15ms in Java with heapsort


  • -1
    Y
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<FEntity> total = new ArrayList<>();
        FEntity[] result = new FEntity[k];
        List<Integer> list = new ArrayList<Integer>(k);
        if (nums.length == 1) {
            list.add(nums[0]);
            return list;
        }
        Map<Integer, FEntity> map = new HashMap<Integer, FEntity>();
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            FEntity fEntity = map.get(a);
            if (fEntity == null) {
                fEntity = new FEntity(a, 1);
                map.put(a, fEntity);
                total.add(fEntity);
    
            } else {
                fEntity.frequent++;
            }
        }
    
        Arrays.fill(result, new FEntity(0, 0));
    
        for (int j = 0, h = total.size(); j < h; j++) {
            insertKeyByHeap(result, total.get(j), k);
        }
        for (int i = 0; i < k; i++) {
            list.add(result[i].num);
    
        }
        return list;
    }
    
    private void insertKeyByHeap(FEntity[] result, FEntity entity, int k) {
        FEntity parent = result[0];
        if (entity.bigger(parent)) {
            result[0] = entity;
            int i = 0;
            int j = 2 * i + 1;
            while (j < k) {
                parent = result[i];
                if (j + 1 < k && result[j].bigger(result[j + 1])) {
                    j++;
                }
                FEntity child = result[j];
                if (parent.bigger(child)) {
                    result[i] = child;
                    result[j] = parent;
                    i = j;
                    j = 2 * i + 1;
                } else
                    break;
            }
        }
    
    }
    
    class FEntity {
        int num, frequent;
    
        public FEntity(int num, int frequent) {
            this.num = num;
            this.frequent = frequent;
        }
    
        public boolean bigger(FEntity arg0) {
            return frequent - arg0.frequent > 0;
        }
    }

  • 0
    S

    class Solution {
    public:

    vector<pair <int,int> > v;
    void swap(int h,int k){
        pair<int,int> tmp = v[k];
        v[k] = v[h];
        v[h] = tmp;
        return;
    }
    
    void insert(pair<int,int> var){
    v.push_back(var);
    int move = v.size()-1;
        while(v[move].second < v[move/2].second){
            swap(move,move/2);
            move = move/2;
        }
        return;
    }
    void del(pair<int,int> var,int k){
        v[1] = var;
        int move = 1;
        while(move <= k){
            if(((move*2) + 1 ) <= k){
                int ind = v[move*2].second < v[(move*2)+1].second ? (move*2) : ((move*2)+1);
                if(v[move].second > v[ind].second){
                    swap(move,ind);
                    move = ind;
                }
                else 
                    break;
            }
            else if(move*2 == k){
                if(v[move].second > v[2*move].second){
                    swap(move,2*move);
                }
                break;
            }
            else
                break;
        }
        return;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> data;
        unordered_map<int,int>::iterator it;
        int i;
        v.push_back(make_pair(0,0));
        for( i=0;i<nums.size();i++){
            if(data.find(nums[i]) == data.end())
                data.insert(pair<int,int>(nums[i],1));
            else
                data[nums[i]] += 1;
        }
        pair<int,int> var;
        it=data.begin();
        for(i=0;i<k;i++){
            var = make_pair(it->first,it->second);
            insert(var);
            it++;
        }
        for(it=it;it!=data.end();it++){
            if(it->second > v[1].second){
                var = make_pair(it->first,it->second);
                del(var,k);
            }
        }
        vector<int> ans;
        for(i=1;i<=k;i++)
            ans.push_back(v[i].first);
        return ans;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.