LeetCode题解——排序

朱雀 2023-06-12 06:28 14阅读 0赞

### 文章目录 ###

*   *  215. 数组中的第K个最大元素
     *   *  直接排序
         *  用堆处理
         *  快速选择
     *  347. 前 K 个高频元素
     *   *  哈希表+排序
         *  hash+heap
     *  451. 根据字符出现频率排序
     *   *  hash+sort
         *  hash+priority\_queue
     *  75. 颜色分类
     *   *  排序双指针

## 215. 数组中的第K个最大元素 ##

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

示例 1:

输入: \[3,2,1,5,6,4\] 和 k = 2  
输出: 5  
示例 2:

输入: \[3,2,3,1,2,4,5,5,6\] 和 k = 4  
输出: 4  
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

### 直接排序 ###

class Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) {
        
            sort(nums.begin(), nums.end());
            return nums[nums.size() - k];
        }
    };

### 用堆处理 ###

维持一个包含k个元素的小顶堆，遍历一遍nums,取出堆顶即可。

class Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) {
        
            priority_queue<int, vector<int>, greater<int>> q;
            for(auto& x : nums)
            {
        
                q.push(x);
                if(q.size() > k)
                    q.pop();
            }
            return q.top();
        }
    };

### 快速选择 ###

利用(从小到大)快排的partition操作把数组两边划分成左边小于等于v, 右边大于等于v。(v为基准值)，位置记为p。 若右边的元素比不少于k个，说明第k大的元素在数组的右边， 否则第k大的元素在数组的左边。  
注意：  
若右边的元素比少于k个，设右边元素个数为lenR，因为右边边已经有lenR个数比现有的位置大了，所以在在数组左边找 第k - lenR大的数。

该递归函数不消耗空间，因为并不需要保存变量。每次平均把数组砍一半，要不递归左边，或者递归右边。

class Solution {
        
    public:
        int partition(vector<int>& nums, int l, int r)
        {
        
            int x = nums[l+r >> 1];
            int i = l - 1, j = r + 1;
            while(i < j)
            {
        
                do ++i; while(nums[i] < x);
                do --j; while(nums[j] > x);
                if(i < j)
                    swap(nums[i], nums[j]);
            }
            return j;
        }
        int find_num(vector<int>& nums, int l, int r, int k)
        {
        
            if(l >= r) return nums[r];
            int p = partition(nums, l, r);
            return (r - p) >= k ? find_num(nums, p + 1, r, k) : find_num(nums, 0, p, k-(r - p));
        }
        int findKthLargest(vector<int>& nums, int k) {
        
            return find_num(nums, 0, nums.size() - 1, k);
        }
    };

平均 时间：O(n) & 空间：O(1) || 最坏：时间：O(n^2) 空间 O(1)

## 347. 前 K 个高频元素 ##

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

示例 1:

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

输入: nums = \[1\], k = 1  
输出: \[1\]  
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。  
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

### 哈希表+排序 ###

统计nums中每个元素的次数，然后根据次数排序，取出前k个就行了。

class Solution {
        
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
        
            vector<int> ans;
            map<int, int> hash;
            for(auto i : nums)
                hash[i]++;
            vector<pair<int, int> > hashv(hash.begin(), hash.end());
            sort(hashv.begin(), hashv.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return a.second > b.second;});
            auto h = hashv.begin();
            while(k--)
            {
        
                ans.push_back(h->first);
                h++;
            }
            return ans;
        }
    };

### hash+heap ###

统计nums中每个元素的次数, 然后维护一个包含k个元素的小顶堆, 每次取出堆顶压入栈。

class Solution {
        
    public:
        struct cmp
        {
        
            bool operator()(pair<int, int>& a, pair<int, int>& b)
            {
        
                return a.second > b.second;
            }
        };
        vector<int> topKFrequent(vector<int>& nums, int k) {
        
            vector<int> ans;
            map<int, int> hash;
            for(auto i : nums)
                hash[i]++;
            priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq;
            for(auto i : hash)
            {
        
                pq.push(i);
                if(pq.size() > k)
                    pq.pop();
            }
            while(k--)
            {
        
                ans.push_back(pq.top().first);
                pq.pop();
            }
            return ans;
        }
    };

## 451. 根据字符出现频率排序 ##

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

示例 1:

输入:  
“tree”

输出:  
“eert”

解释:  
'e’出现两次，'r’和’t’都只出现一次。  
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。  
示例 2:

输入:  
“cccaaa”

输出:  
“cccaaa”

解释:  
'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。  
注意"cacaca"是不正确的，因为相同的字母必须放在一起。  
示例 3:

输入:  
“Aabb”

输出:  
“bbAa”

解释:  
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。  
注意’A’和’a’被认为是两种不同的字符。

### hash+sort ###

记录每个字符出现的次数，然后按次数从大到小排序，最后输出。

class Solution {
        
    public:
        string frequencySort(string s) {
        
            map<char, int> h;
            for(auto c : s)
            {
        
                h[c]++;
            }
            vector<pair<char, int> > v(h.begin(), h.end());
            sort(v.begin(), v.end(), [](pair<char, int>& a, pair<char, int>& b) {
        return a.second > b.second;});
            string ans = "";
            vector<pair<char, int> >::iterator v1 = v.begin();
            for(; v1 != v.end(); v1++)
            {
        
                while(v1->second--) ans += v1->first;
            }
            return ans;
        }
    };

### hash+priority\_queue ###

记录每个字符出现的次数, 然后维护一个大顶堆，每次取出堆顶出去就好了。

class Solution {
        
    public:
        struct cmp
        {
        
            bool operator()(pair<char, int>& a, pair<char, int>& b)
            {
        
                return a.second < b.second;
            }
        };
        string frequencySort(string s) {
        
            map<char, int> h;
            for(auto c : s)
            {
        
                h[c]++;
            }
            priority_queue<pair<char, int>, vector<pair<char, int> >, cmp> pq;
            for(auto i : h)
                pq.push(i);
            int n = pq.size();
            string ans = "";
            while(n--)
            {
        
                int j = pq.top().second;
                while(j--) ans += pq.top().first;
                pq.pop();
            }
            return ans;
        }
    };

## 75. 颜色分类 ##

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

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

注意:  
不能使用代码库中的排序函数来解决这道题。

示例:

输入: \[2,0,2,1,1,0\]  
输出: \[0,0,1,1,2,2\]  
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。  
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。  
你能想出一个仅使用常数空间的一趟扫描算法吗？

### 排序双指针 ###

class Solution {
        
        public void sortColors(int[] nums) {
        
            int p1 = 0, p2 = nums.length - 1, cur = 0;
            while(cur <= p2){
        
                if(nums[cur] == 1){
        
                    cur++;
                }else if(nums[cur] == 0){
        
                    int tmp = nums[p1];
                    nums[p1++] = nums[cur];
                    nums[cur++] = tmp;
                }else{
        
                    int tmp = nums[p2];
                    nums[p2--] = nums[cur];
                    nums[cur] = tmp;
                }
            }
        }
    }

![format_png][]

[format_png]: /images/20230531/ca2fcf94ceef4b05baa815d72e08ddb9.png