算法排序算法

快速排序

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) {Map<Integer, Integer> map = new HashMap<>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}List<Integer>[] list = new List[nums.length + 1];for (int num : map.keySet()) {int count = map.get(num);if (list[count] == null) {list[count] = new ArrayList<Integer>();}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;}
}