LeetCode——排序

男娘i 2023-06-15 14:27 3阅读 0赞

# 排序 #

--------------------

## 目录 ##

1.  快速选择
2.  堆
3.  桶排序之出现频率最多的k个元素
4.  桶排序之按照字符出现次数对字符串排序
5.  荷兰国旗问题

--------------------

### 1. 快速选择 ###

用于解 Kth Element 问题，也就是第 k 个元素的问题。

可以用快速排序的 partition() 进行实现。需要先打乱数组，否则最坏情况下时间复杂度为 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;
                else
                    end = pos - 1;
            }
            return nums[k - 1];
        }
    
        public int partition(int[] nums, int l, int r) {
        
            int less = l - 1;//小于区的下标
            int more = r;//大于区的下标，默认以最后一个下标的数作为划分值
            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;//小于区位置+1可以得到划分的这个数的下标
        }
    
        private void swap(int[] arr, int i, int j) {
        
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }

需要去重的话可以利用HashSet或其他数据结构得到所有唯一的数字，然后使用本算法处理。

--------------------

### 2. 堆 ###

用于求解 TopK Elements 问题，也就是 K 个最小元素的问题。可以维护一个大小为 K 的最小堆，最小堆中的元素就是最小元素。最小堆需要使用大顶堆来实现，大顶堆表示堆顶元素是堆中最大元素。这是因为我们要得到 k 个最小的元素，因此当遍历到一个新的元素时，需要知道这个新元素是否比堆中最大的元素更小，更小的话就把堆中最大元素去除，并将新元素添加到堆中。所以我们需要很容易得到最大元素并移除最大元素，大顶堆就能很好满足这个要求。

堆也可以用于解决 Kth Element 问题，得到了大小为 k 的最小堆之后，因此使用了大顶堆来实现，因此堆顶元素就是第 k 大的元素。

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

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

![在这里插入图片描述][20191123114043662.png]  
排序：时间复杂度 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 findKthLargest1(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();
        }

--------------------

### 3. 桶排序 ###

###### 1. 之出现频率最多的k个元素 ######

![在这里插入图片描述][2019112317501066.png]  
设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。

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

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. 按照字符出现次数对字符串排序 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

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. 荷兰国旗问题 ###

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

有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排序。它其实是三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素，等于切分元素，大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。

###### 1. 按颜色进行排序 ######

![在这里插入图片描述][20191124150335787.png]  
题目描述：只有 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;
        }

[20191123114043662.png]: https://img-blog.csdnimg.cn/20191123114043662.png
[2019112317501066.png]: https://img-blog.csdnimg.cn/2019112317501066.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/201911241354584.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[20191124150335787.png]: https://img-blog.csdnimg.cn/20191124150335787.png