网站 维护费用,如何做拼车网站app,承德市官网,一同看网页打不开文章目录 快速排序[leetcode 215数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/)分析题解快速排序 桶排序[leetcode 347 前K个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)分析题解 快速排序
leetcode 215数组… 文章目录 快速排序[leetcode 215数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/)分析题解快速排序 桶排序[leetcode 347 前K个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)分析题解 快速排序
leetcode 215数组中的第K个最大元素
分析
对于这种“第K个元素”的问题可以用快速选择它是对快速排序的一种简化。快速排序采用分治思想将数组分为两个子数组每次划分数组都随机选择一个元素小于该元素的在一个数组大于该元素的在另一个数组。递归执行划分数组操作直到数组全部完成排序。 而快速选择针对某个元素它不要求对两个子数组排序仅仅递归划分“第K个元素”在的那个子数组即可直到获得“第K个元素”的位置。为了避免两个子数组一个长度为1一个长度为n-1的极端情况每次划分数组时随机选择元素。
题解
class Solution {static Random random new Random();public int findKthLargest(int[] nums, int k) {int n nums.length;int target n - k;int left 0;int right n - 1;while(true) {int pivot partition(nums, left, right);if (pivot target) {return nums[pivot];} else if (pivot target) {left pivot 1;} else {right pivot - 1;}}}private int partition(int[] nums, int left, int right) {int randomIndex left random.nextInt(right - left 1);swap(nums, randomIndex, left);int l left 1;int r right;while (true) {while (l r nums[r] nums[left] ) {r--;}while (l r nums[l] nums[left] ) {l; }if (l r) {break;}swap(nums, l, r);l;r--;}swap(nums, left, r);return r;}private void swap(int[] nums, int i1, int i2) {int temp nums[i1];nums[i1] nums[i2];nums[i2] temp;}
}快速排序
quickSort通过递归实现快速排序。
class Solution {static Random random new Random();public void quickSort(int[] nums, int left, int right) {if (left right) {int index partition(nums, left, right);quickSort(nums, left, index - 1);quickSort(nums, index 1, right);}}private int partition(int[] nums, int left, int right) {int randomIndex left random.nextInt(right - left 1);swap(nums, randomIndex, left);int l left 1;int r right;while (true) {while (l r nums[r] nums[left] ) {r--;}while (l r nums[l] nums[left] ) {l; }if (l r) {break;}swap(nums, l, r);l;r--;}swap(nums, left, r);return r;}private void swap(int[] nums, int i1, int i2) {int temp nums[i1];nums[i1] nums[i2];nums[i2] temp;}
}桶排序
leetcode 347 前K个高频元素
分析
首先统计元素频次之后对频次建桶桶里内容是该频次对应的元素们。最后根据频次高低返回K个元素。
题解
class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger, Integer map new HashMap();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}ListInteger[] list new List[nums.length 1];for (int num : map.keySet()) {int count map.get(num);if (list[count] null) {list[count] new ArrayListInteger();}list[count].add(num);}int[] res new int[k];int idx 0;for (int i list.length - 1; i 0 idx k; i--) {if (list[i] null ) {continue;}while (!list[i].isEmpty()) {res[idx] list[i].getLast();list[i].removeLast();}}return res;}
}
