347. 前 K 个高频元素

347. 前 K 个高频元素

1.想法

利用Map存储每个数的频次,<key,value>-><num,frequency>,然后将数据读出,存储在两个int的数组里面,一个int[] tag代表了这个数字,然后int[] frequency代表了数字的频次,然后根据frequency调整tag,利用frequency建立大根堆或者小根堆,输出前k或者后k个数.
堆排序:https://www.jianshu.com/p/1977402d9277

2.代码

public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<>();
        Map<Integer,Integer> res = new HashMap<>();
        //先记录每个数字的频次
        for(int i=0;i<nums.length;i++){
            res.put(nums[i],res.getOrDefault(nums[i],0)+1);
        }
        int[] tags = new int[res.size()];
        int[] frequency = new int[res.size()];
        int i = 0;
        Iterator iterator = res.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry item = (Map.Entry) iterator.next();
            tags[i] = (int) item.getKey();
            frequency[i++] = (int) item.getValue();
        }
        builtMinHeap(tags,frequency,k);
        for(int index = tags.length-1;index>tags.length-1-k;index--){
            result.add(tags[index]);
        }
        return result;
    }
    //建立小根堆,当后k个数排序完成时,算法结束
    private void builtMinHeap(int[] tags, int[] frequency, int k) {
        int count = 0;
        for(int i=tags.length/2-1;i>-1;i--){
            dealSnap(tags,frequency,i,tags.length);
        }
        while(count<k){
            swap(tags,frequency,tags.length-1-count,0);
            dealSnap(tags,frequency,0,tags.length-1-count);
            count++;
        }
    }
   //调整过程
    private void dealSnap(int[] tags, int[] frequency, int start, int end) {
       if(2*start+1>=end){
           return;
       }else if(2*(start+1)>=end){
           if(frequency[2*start+1]>=end){
               swap(tags,frequency,2*start+1,start);
           }
       }else{
           if(frequency[start]>=frequency[2*start+1]&&frequency[start]>=frequency[2*(start+1)]){
               return;
               //左子树最大,交换后去排列左边
           }else if(frequency[2*start+1]>=frequency[start]&&frequency[2*start+1]>=frequency[2*(start+1)]){
               swap(tags,frequency,2*start+1,start);
               dealSnap(tags,frequency,2*start+1,end);
               //右子树最大，交换后去排列右边
           }else{
               swap(tags,frequency,2*(start+1),start);
               dealSnap(tags,frequency,2*(start+1),end);
           }
       }
    }
  //交换过程
    private void swap(int[] tags, int[] frequency, int i, int j) {
        int tempTag = tags[i];
        int tempFraquency = frequency[i];
        tags[i] = tags[j];
        frequency[i] = frequency[j];
        tags[j] = tempTag;
        frequency[j] = tempFraquency;
    }