Kosmos Kosmos

---我们总得选择一条路去前行---

目录
Leetcode之排序(部分)
/  

Leetcode之排序(部分)

导航:
快速排序 堆排序 桶排序 荷兰国旗问题

友情提示: 代码在这里
本文参照该仓库学习,大家可以star

快速选择

用于求解 Kth Element 问题,使用快速排序的 partition() 进行实现。

需要先打乱数组,否则最坏情况下时间复杂度为 O(N2)。

堆排序

用于求解 TopK Elements 问题,通过维护一个大小为 K 的堆,堆中的元素就是 TopK Elements。

堆排序也可以用于求解 Kth Element 问题,堆顶元素就是 Kth Element。

快速选择也可以求解 TopK Elements 问题,因为找到 Kth Element 之后,再遍历一次数组,所有小于等于 Kth Element 的元素都是 TopK Elements。

可以看到,快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。

排序 :时间复杂度 O(NlogN),空间复杂度 O(1)

public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }

堆排序 :时间复杂度 O(NlogK),空间复杂度 O(K)。

public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆 for (int val : nums) { pq.add(val); if (pq.size() > k) // 维护堆的大小为 K pq.poll(); } return pq.peek(); }

快速选择 :时间复杂度 O(N),空间复杂度 O(1)

public int findKthLargest(int[] nums, int k) { k = nums.length - k; int l = 0, h = nums.length - 1; while (l < h) { int j = partition(nums, l, h); if (j == k) { break; } else if (j < k) { l = j + 1; } else { h = j - 1; } } return nums[k]; } private int partition(int[] a, int l, int h) { int i = l, j = h + 1; while (true) { while (a[++i] < a[l] && i < h) ; while (a[--j] > a[l] && j > l) ; if (i >= j) { break; } swap(a, i, j); } swap(a, l, j); return j; } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

桶排序

出现频率最多的 k 个数

设置若干个桶,每个桶存储出现频率相同的数,并且桶的下标代表桶中数出现的频率,即第 i 个桶中存储的数出现的频率为 i。

把数都放到桶之后,从后向前遍历桶,最先得到的 k 个数就是出现频率最多的的 k 个数。

按照字符出现次数对字符串排序

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

荷兰国旗问题

荷兰国旗包含三种颜色:红、白、蓝。

有三种颜色的球,算法的目标是将这三种球按颜色顺序正确地排列。

其实是三向切分快速排序的一种变种,在三向切分快速排序中,每次切分都将数组分成三个区间:小于切分元素、等于切分元素、大于切分元素,而该算法是将数组分成三个区间:等于红色、等于白色、等于蓝色。

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

public void sortColors(int[] nums) { int zero = -1, one = 0, two = nums.length; while (one < two) { if (nums[one] == 0) { swap(nums, ++zero, one++); } else if (nums[one] == 2) { swap(nums, --two, one); } else { ++one; } } } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }

快速排序的思想 nums[one]指向中间的数 中间的数比左边小就swap 比右边大就swap 左边的和中间的排序 中间和右边的排序 (这里只有三个数)


今日诗词 标题:Leetcode之排序(部分)
作者:ellenbboe
地址:https://ellenbboe.github.io/articles/2019/04/15/1561009690183.html