📸排序📸

堆排序、快速排序

建立哈希表并排序

荷兰国旗问题

数组中的第K个最大元素

leetcode在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

使用SLT库排序

1
2
3
4
int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
}

堆排序解题思路

  • 堆排序会使用到优先队列priority_queue，可以当成一种高级队列，只不过这个队列是已经排好序的。
  • 维护一个个数为k的小顶堆，堆从从上到下按从小到大排序
  • 始终保持堆的大小为k，超出k就pop(),直到遍历结束位置，堆中存放着前k个最大元素，堆顶的元素就是正确答案。
    1
    2
    3
    4
    5
    6
    7
    8
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > queue;
        for (auto it : nums) {
            queue.push(it);
            if (queue.size() > k) queue.pop();
        }
        return queue.top();
    }

    快速排序解题思路

  • 不使用STL库的情况下，手写一个快速排序算法
  • 注意：快速排序使用的是递归，所以记得一定要写个递归结束条件if (left > right) return ;。
  • 注意：在partition函数中while里处理要判断nums[right] >= p，还要判断left < right。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums, 0, nums.size() - 1);
        return nums[nums.size() - k];
    }

    void quickSort(vector<int>& nums, int left, int right) {
        if (left > right) return ;
        int mid = partition(nums, left, right);
        quickSort(nums, left, mid - 1);
        quickSort(nums, mid + 1,right);
    }

    int partition(vector<int>& nums, int left, int right) {
        int p = nums[left];
        while (left < right) {
            while (nums[right] >= p && left < right) right--;
            nums[left] = nums[right];
            while (nums[left] <= p && left < right) left++;
            nums[right] = nums[left];
        }
        nums[left] = p;
        return left;
    }

前K个高频元素

leetcode给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

解题思路

  • 建立哈希表统计数字出现频率，
  • 利用隐式转换，把无序hash转换为pair类型方便按照频率多少进行排序
  • 使用SLT的sort()函数进行排序，大小的比较规则cmp函数需要自己写。
  • 将排好序的前k元素输出
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    static bool cmp(pair<int, int> v1, pair<int, int> v2){
        return v1.second > v2.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            hash[nums[i]]++;
        }
        vector<pair<int, int> > arr(hash.begin(), hash.end());
        sort(arr.begin(), arr.end(), cmp);
        vector<int> res;
        for(int i = 0; i < k; ++i){
            res.push_back(arr[i].first);
        }
        return res;
    }

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

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

解题思路

  • 哈希表建立的频率表是无序的，所以需要转换为其他数据结构，再使用排序算法对其排序
  • 可以使用隐式的类型转换为pair<char,int>，再使用STL里面的sort()函数进行排序，sort的好处是可以自定义排序的规则。
  • sort()函数自定义的排序规则需要写成静态的函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    static bool cmp(pair<char, int> a, pair<char, int> b) {
        return a.second > b.second;
    }
    string frequencySort(string s) {
        unordered_map<char, int>hash;
        for (auto it : s) {
            hash[it]++;
        }
        vector<pair<char, int> > arr(hash.begin(), hash.end());
        sort(arr.begin(), arr.end(), cmp);
        string res;
        for (auto it : arr) {
            while (it.second--) {
                res.push_back(it.first);
            }
        }
        return res;
    }

荷兰国旗

Leetcode给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

解题思路

  • 一共三个指针，p0一直指向0的后一位，p2一直指向2的前一位，cur是用于遍历的指针。
  • 本题属于荷兰旗帜问题：思想是遇到0就跟p0所指的数交换位置，遇到2就跟p2所指的数交换位置，遇到1就跳过。
  • 注意：遇到2交换完位置后，cur指针不前进，因为要再次判断交换过来的数是0还是1。
  • 注意2：while结束是 cur < p2而不是cur < nums.size() 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void sortColors(vector<int>& nums) {
        int p0 = 0, p2 = nums.size() - 1;
        int cur = 0;
        while (cur < p2) {
            if (nums[cur] == 1) cur++;
            else if (nums[cur] == 0) swap(nums[p0++], nums[cur++]);
            else if (nums[cur] == 2) swap(nums[cur],nums[p2--]);
        }
    }