JAVA solution beats 99.95%


  • 1
    Z

    I wouldn't expect it to run fast because I think I waste too much time on sorting and object/space creation. The result is a bit mindblowing.
    This algorithm borrowed the idea from the solution to H-Index.
    I think there's actually a flaw in the code, but it still passed all the test cases. I should remind you if you wanna use it. Think that if you have [1,1,1,2,2,2,3,3,3,4] with k = 2, then what will be the result

    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > max) max = nums[i];
                if (nums[i] < min) min = nums[i];
            }
            
            if (min > 0) min = 0;
            int[] count = new int[max - min + 1];
            for (int i = 0; i < count.length; i++) count[i] = 0;
    
            for (int i = 0; i < nums.length; i++) {
                count[nums[i] - min]++;
            }
            
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < count.length; i++) {
                if (map.containsKey(count[i])) map.get(count[i]).add(i);
                else {
                    List<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(i);
                    map.put(count[i], tmp);
                }
            }
            Arrays.sort(count);
            List<Integer> result = new ArrayList<>();
            while (k != 0) {
                List<Integer> r = map.get(count[count.length - 1 - --k]);
                k -= r.size() - 1;
                for (int a : r) result.add(a + min);
            }
            return result;
        }
    }
    

    Comments are welcomed!!


Log in to reply
 

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