排序

---

目錄

快速選擇

堆

桶排序之出現(xiàn)頻率最多的k個(gè)元素

桶排序之按照字符出現(xiàn)次數(shù)對(duì)字符串排序

荷蘭國(guó)旗問(wèn)題

---

1. 快速選擇

用于解 Kth Element 問(wèn)題，也就是第 k 個(gè)元素的問(wèn)題。

可以用快速排序的 partition() 進(jìn)行實(shí)現(xiàn)。需要先打亂數(shù)組，否則最壞情況下時(shí)間復(fù)雜度為 O(N^2 )。

public int findKthLargest(int[] nums, int k) {int begin = 0;int end = nums.length - 1;k = nums.length + 1 - k;while (begin < end) {int pos = partition(nums, begin, end);if (pos == k - 1)break;else if (pos < k - 1)begin = pos + 1;elseend = pos - 1;}return nums[k - 1];}public int partition(int[] nums, int l, int r) {int less = l - 1;//小于區(qū)的下標(biāo)int more = r;//大于區(qū)的下標(biāo)，默認(rèn)以最后一個(gè)下標(biāo)的數(shù)作為劃分值while (l < more) {if (nums[l] < nums[r])swap(nums, ++less, l++);else if (nums[l] > nums[r])swap(nums, --more, l);else l++;}swap(nums, more, r);return less + 1;//小于區(qū)位置+1可以得到劃分的這個(gè)數(shù)的下標(biāo)}private void swap(int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}

需要去重的話可以利用HashSet或其他數(shù)據(jù)結(jié)構(gòu)得到所有唯一的數(shù)字，然后使用本算法處理。

---

2. 堆

用于求解 TopK Elements 問(wèn)題，也就是 K 個(gè)最小元素的問(wèn)題。可以維護(hù)一個(gè)大小為 K 的最小堆，最小堆中的元素就是最小元素。最小堆需要使用大頂堆來(lái)實(shí)現(xiàn)，大頂堆表示堆頂元素是堆中最大元素。這是因?yàn)槲覀円玫?k 個(gè)最小的元素，因此當(dāng)遍歷到一個(gè)新的元素時(shí)，需要知道這個(gè)新元素是否比堆中最大的元素更小，更小的話就把堆中最大元素去除，并將新元素添加到堆中。所以我們需要很容易得到最大元素并移除最大元素，大頂堆就能很好滿足這個(gè)要求。

堆也可以用于解決 Kth Element 問(wèn)題，得到了大小為 k 的最小堆之后，因此使用了大頂堆來(lái)實(shí)現(xiàn)，因此堆頂元素就是第 k 大的元素。

快速選擇也可以求解 TopK Elements 問(wèn)題，因?yàn)檎业?Kth Element 之后，再遍歷一次數(shù)組，所有小于等于 Kth Element 的元素都是 TopK Elements。

可以看到，快速選擇和堆排序都可以解決 Kth Element 和 TopK Elements 問(wèn)題。

排序：時(shí)間復(fù)雜度 O(NlogN)，空間復(fù)雜度 O(1)

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

堆：時(shí)間復(fù)雜度 O(NlogK)，空間復(fù)雜度 O(K)。

public int findKthLargest1(int[] nums, int k) {PriorityQueue<Integer> pq = new PriorityQueue<>(); //小頂堆for (int val : nums) {pq.add(val);if (pq.size() > k) { //維護(hù)堆的大小為 Kpq.poll();}}return pq.peek();}

---

3. 桶排序

1. 之出現(xiàn)頻率最多的k個(gè)元素

設(shè)置若干個(gè)桶，每個(gè)桶存儲(chǔ)出現(xiàn)頻率相同的數(shù)。桶的下標(biāo)表示數(shù)出現(xiàn)的頻率，即第 i 個(gè)桶中存儲(chǔ)的數(shù)出現(xiàn)的頻率為 i。

把數(shù)都放到桶之后，從后往前遍歷，最先得到的 k 個(gè)數(shù)就是出現(xiàn)頻率最多的 k 個(gè)數(shù)。

public static List<Integer> topKFrequent(int[] nums, int k) {Map<Integer, Integer> frequencyForNum = new HashMap<>();for (int num : nums) {frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1);}List<Integer>[] buckets = new ArrayList[nums.length + 1];for (Integer key : frequencyForNum.keySet()) {int frequency = frequencyForNum.get(key);if (buckets[frequency] == null) {buckets[frequency] = new ArrayList<>();}buckets[frequency].add(key);}List<Integer> topK = new ArrayList<>();for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {if (buckets[i] == null) {continue;}if (buckets[i].size() <= (k - topK.size())) {topK.addAll(buckets[i]);} else {topK.addAll(buckets[i].subList(0, k - topK.size()));}}return topK;}

---

2. 按照字符出現(xiàn)次數(shù)對(duì)字符串排序

public String frequencySort(String s) {Map<Character, Integer> map = new HashMap<>();for (char c : s.toCharArray()) {map.put(c, map.getOrDefault(c, 0) + 1);}List<Character>[] buckets = new ArrayList[s.toCharArray().length + 1];for (Character c : map.keySet()) {Integer value = map.get(c);if (buckets[value] == null) {buckets[value] = new ArrayList<>();}buckets[value].add(c);}StringBuilder str = new StringBuilder();for (int i = buckets.length - 1; i >= 0; i--) {if (buckets[i] == null) {continue;}for (Character character : buckets[i]) {for (int j = 0; j < i; j++) {str.append(character);}}}return str.toString();}

---

5. 荷蘭國(guó)旗問(wèn)題

荷蘭國(guó)旗包含三種顏色：紅、白、藍(lán)。

有三種顏色的球，算法的目標(biāo)是將這三種球按顏色順序正確地排序。它其實(shí)是三向切分快速排序的一種變種，在三向切分快速排序中，每次切分都將數(shù)組分成三個(gè)區(qū)間：小于切分元素，等于切分元素，大于切分元素，而該算法是將數(shù)組分成三個(gè)區(qū)間：等于紅色、等于白色、等于藍(lán)色。

1. 按顏色進(jìn)行排序

題目描述：只有 0/1/2 三種顏色。

public void sortColors(int[] nums) {int zero = -1;int one = 0;int 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;}

總結(jié)

以上是生活随笔為你收集整理的LeetCode——排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。