文章目录

347-前 K 个高频元素

topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是 nlogk
避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。

[注意]

求前 k 大，用小根堆，求前 k 小，用大根堆。面试的时候如果说反了会挂！

  • topk 复杂度不是 klogk，是 nlogk.

  • 建堆，假设数组大小是 n, 执行 n 次 sink 操作，每次操作复杂度是 logn，因此建堆复杂度是 nlogn.

  • 插入，logn，上浮操作。

  • 删除（堆顶），一次 sink 操作，logn.

// 利用i 这个trick,记录了最大出现的频率值，然后逐渐减少i, 直到找到第二小的频率值， 但是这个方法适用于频率值差异比较小的情况，如果频率值差异很大， 那么会无用的遍历map很多遍，而找不到对应的频率值
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        vector<int> res;
        int i=0;
        for(auto num:nums)
            i = max(i,++m[num]);
        
        while(res.size()<k){
            for(auto p:m){
                if(p.second == i)
                    res.push_back(p.first);
            }
            --i;
        }
      return res;   
    }
};

优先队列

**

  • 有限队列说到底还是队列，只不过优先队列的top指向优先级比较高的元素，而队列的top就是指向队首；

  • 如果要取前k个最大的元素，则需要优先队列最小堆排序，既top永远指向最小的元素，如果新添加的元素大于当前队列最小的元素，则出队列，并且push新元素，这样遍历一遍后，保证队列中的元素为前k个最大的元素

  • 如果要取前k个最小的元素，则需要优先队列最大堆排序，既top指向最大的元素，如果新添加的元素小于最大元素，则出队列，push新元素，这样保证队列中为最小的元素

// 利用优先队列的特性，首先弹出优先级比较高的元素
vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        vector<int> res;
        int i=0;
        for(auto num:nums)
            m[num]++;
         priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
         
         for(auto p:m){
             if(pq.size() == k){
                 
                 if(p.second > pq.top().first){
                     pq.pop();
                     pq.push( make_pair(p.second,p.first));
                 }
                 
             }else{
                 pq.push( make_pair(p.second,p.first));
             }   
         }
         
         while(!pq.empty()){
             res.push_back(pq.top().second);
             pq.pop();
         }
         
      return res;   
    }

优先队列的使用

优先队列低层默认为最大堆，既队首对排序最大的元素 在优先队列中，优先级高的元素先出队列。

它的模板声明带有三个参数，priority_queue<Type, Container, Functional>

  • Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
  • Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.
  • STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。 
//priority_queue <> 元素，
#include<iostream>
#include<queue>
#include<cstdlib>
using namespace std;
struct Node{
	int x,y;
	Node(int a=0, int b=0):
		x(a), y(b) {}
};
 
struct cmp{
	bool operator()(Node a, Node b){
		if(a.x == b.x)	return a.y>b.y;
		return a.x>b.x;
	}
};
 
int main(){
	priority_queue<Node, vector<Node>, cmp>p;
	
	for(int i=0; i<10; ++i)
		p.push(Node(rand(), rand()));
		
	while(!p.empty()){
		cout<<p.top().x<<' '<<p.top().y<<endl;
		p.pop();
	}//while
	//getchar();
	return 0;

根据字符出现频率排序

输入: "tree"
输出: "eert"

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

class Solution {
public:
    string frequencySort(string s) {
        int i=0;
        unordered_map<char,int> m;
        for(auto c:s)
             i = max(i,++m[c]);
        string res = "";
        while(res.size()<s.size()){
            
            for(auto p:m){
                if(p.second == i){
                    for(int j=0;j<i;j++)
                        res+=p.first;
                }
            }
            --i;
        }
        
        return res;
    }
};

692. 前K个高频单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

class Solution {
public:
    
    struct cmp
    { 
        bool operator()(pair<string,int>a,pair<string,int>b){
            if(a.second<b.second)
                return true;
            else if(a.second>b.second)
                return false;
            return a.first>b.first;
        }    
    };
    
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res;
        map<string,int> m;
        for(auto s:words)
            m[s]++;
        priority_queue< pair<string,int>, vector<pair<string,int>>,cmp > pq;
        
        for(auto p:m)
            pq.push(p);
        
        int index=0;
        while(!pq.empty()&&index++!=k){
            res.push_back(pq.top().first);
            pq.pop();
        }
        return res;
	}
};

973 最接近0的点

解法1

// 直接修改sort排序函数的 comp比较函数，然后取前k个最小的元素
class Solution {
public:
    
    static bool cmp(vector<int>&a, vector<int>&b) {        //排序方法
		 return sqrt(pow(a[0], 2) + pow(a[1], 2)) < sqrt(pow(b[0], 2) + pow(b[1], 2));
	 }
    
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        vector<vector<int>> res;
        sort(points.begin(), points.end(), cmp);
        return vector<vector<int>>(points.begin(), points.begin() + K);
    }
};


class Solution {
public:
    
    struct cmp{
         bool operator()(vector<int> a,vector<int> b){
             return sqrt(pow(a[0], 2) + pow(a[1], 2)) < sqrt(pow(b[0], 2) + pow(b[1], 2));
         }  
     };
    
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        vector<vector<int>> res;
         priority_queue< vector<int>, vector<vector<int>>, cmp > pq;
        
         for(int i=0;i<points.size();i++){
            if(pq.size() < K)           
                pq.push(make_pair(distance2(points[i]), i));
            else if(distance2(points[i]) < pq.top().first)
            {
                pq.pop();
                pq.push(make_pair(distance2(points[i]), i));
            }
        }
        
        int index = 0;
        while(!pq.empty()&&index++!=K){
            res.push_back(points[pq.top().second]);
            pq.pop();
        }
        return res;
    }
};

1046. 最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
使用优先队列 动态保持数组有序

不使用优先队列的话，每次更新都需要重新sort

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> mp;
        for(int i:stones)
            mp.push(i);
        
        while(mp.size() > 1){
            int x = mp.top();
            mp.pop();
            int y = mp.top();
            mp.pop();
            if(x==y) continue;
            if(x!=y) mp.push(x-y);
        }
        if(!mp.empty()) return mp.top();
        else return 0;
    }
};

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

c++ 快排 每个案列都随机化一下 避免极端案例

记得快排前，对数组随机化一下，避免极端案例，退化成 O(N^2)冒泡算法

非递归

class Solution {
public:
    int partition(vector<int>& nums,int left,int right){
        int randIndex = rand()%(right-left+1)+left;
        swap(nums[left], nums[randIndex]);
        int key = nums[left];

        while(left<right){
            while(left<right && nums[right] >= key) right--;
            nums[left] = nums[right];
            while(left<right && nums[left] <= key) left++;
            nums[right] = nums[left];
        }
        nums[left] = key;
        return left;
    }

    int findKthLargest(vector<int>& nums, int k) {
        
        int len = nums.size();
        if(!len) return 0;

        srand(time(NULL));

        typedef pair<int,int> P;
        stack<P> ms;
        ms.push(P(0,len-1));
        while(!ms.empty()){
            int left = ms.top().first;
            int right = ms.top().second;
            ms.pop();
            if(left > right) continue;
            
            int mid = partition(nums,left,right);
            if(mid == len-k){
                return nums[mid];
                break;
            }
            if(mid < len-k) ms.push(P(mid+1,right));
            else ms.push(P(left,mid-1));
        }

        return -1;
    }
};

递归

class Solution {
public:
    int partition(vector<int>& nums,int left,int right){
        int randIndex = rand()%(right-left+1)+left;
        swap(nums[left], nums[randIndex]);
        int key = nums[left];

        while(left<right){
            while(left<right && nums[right] >= key) right--;
            nums[left] = nums[right];
            while(left<right && nums[left] <= key) left++;
            nums[right] = nums[left];
        }
        nums[left] = key;
        return left;
    }

    int dfs(vector<int>& nums, int left,int right,int k){
        if(left > right) return -1;
        int mid = partition(nums,left,right);
        if(mid == nums.size()-k) return nums[mid];
        else if(mid < nums.size()-k) return dfs(nums,mid+1,right,k);
        else return dfs(nums,left,mid-1,k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        
        int len = nums.size();
        if(!len) return 0;

        srand(time(NULL));
        return dfs(nums,0,len-1,k);
    }
};

小顶堆

  • 手动维护一个大小为k小顶堆，最后弹出堆顶元素 即为小顶堆中最小的元素 也是整个数组中第k大的元素 
class Solution {
public:
    void adjust_heap(vector<int>& nums,int index){
        int left = 2*index + 1;
        int right = 2*index + 2;
        int len = nums.size();
        int maxindex =index;

        if(left<len && nums[left] < nums[maxindex]) maxindex = left;
        if(right<len && nums[right] < nums[maxindex]) maxindex = right;
        if(index!=maxindex){
            swap(nums[index],nums[maxindex]);
            adjust_heap(nums,maxindex);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        int res = 0;
        if(len<0) return res;
        
        vector<int> tmp(nums.begin(),nums.begin()+k);

        for(int i=tmp.size()/2;i>=0;i--)
            adjust_heap(tmp,i);
        
        for(int i=k;i<len;i++){
            if(nums[i] > tmp[0]){
                tmp[0] = nums[i];
                adjust_heap(tmp,0);
            }
        }
        return tmp[0];
    }
};