Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

这道题要找到出现次数从多到少排的前k个元素。
首先我想到的是使用一个map来保存所有的元素出现的次数，然后遍历这个map找到前k个。
怎么遍历这个map呢，首先想到的是把它读到一个数组里然后排序：

var topKFrequent = function(nums, k) {
    var map = {};
    var result = [];
    for (var i = 0;i < nums.length;i++) {
        if (map[nums[i]]===undefined)
            map[nums[i]]=1;
        else {
            map[nums[i]]++;
        }
    }
    for (var item in map) {
        result.push([item,map[item]]);
    }
    result.sort(function(a,b){
        return -(a[1]-b[1]);
    });
    for (i = 0; i < k;i++) {
        result[i] = parseInt(result[i][0]);
    }
    return result.slice(0,k);
};

不过还有个更好的办法，所有元素出现的顺序都不会大于n，所以我们建一个长度为n+1的数组，用下标来表示没个元素出现的次数，由于会有多个元素出现相同的次数，所以这会是个二维数组。
最后从后往前遍历这个数组，取出k个数就好。
这样就不用排序了。

var topKFrequent = function(nums, k) {
    var map = {};
    var result = [];
    var res = [];
    for (var i = 0;i < nums.length;i++) {
        if (map[nums[i]]===undefined)
            map[nums[i]]=1;
        else {
            map[nums[i]]++;
        }
    }
    for (var item in map) {
        if (result[map[item]]!==undefined) 
            result[map[item]].push(item);
        else
            result[map[item]] = [item];
    }
    var num = result.length-1;
    var count = 0;
    while(count!==k) {
        if (result[num]!==undefined) {
            for (i=0; i<result[num].length;i++) {
                res.push(parseInt(result[num][i]));
                count++;
            }
        }
        num--;
    }
    return res;
};