Java - 45ms solution with two helper methods


  • -1
    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer>result = new ArrayList<Integer>();
            
            // data sorting and filtering
            Map<Integer, Integer>mostFrequest = buildFreqMap(nums);
            TreeMap<Integer, List<Integer>>mostFrequestSorted = getSortedByValueMap(mostFrequest);
            // main logic
            for(Integer key : mostFrequestSorted.descendingKeySet()){
                result.addAll(mostFrequestSorted.get(key));
                if(result.size() >=k)
                    break;
            }
           // System.out.println(mostFrequestSorted.descendingMap());
            return result;
        }
        
        public static TreeMap<Integer, List<Integer>> getSortedByValueMap(final Map<Integer, Integer>mostFrequest){
            TreeMap<Integer, List<Integer>>mostFrequestSorted = new TreeMap<Integer, List<Integer>>();
            for(Map.Entry<Integer, Integer> entry : mostFrequest.entrySet()){
                if(mostFrequestSorted.get(entry.getValue()) == null)
                    mostFrequestSorted.put(entry.getValue(), new ArrayList<Integer>());
                
                mostFrequestSorted.get(entry.getValue()).add(entry.getKey());
            }
            return mostFrequestSorted;
        }
        
        public static Map<Integer, Integer> buildFreqMap(int[]nums){
            Map<Integer, Integer>mostFrequest = new HashMap<Integer, Integer>();
            
            for(int i = 0; i < nums.length; i++){
                if(mostFrequest.get(nums[i]) == null)
                    mostFrequest.put(nums[i], 1);
                else{
                    int val = mostFrequest.get(nums[i])+1;
                    mostFrequest.put(nums[i], val);
                }
            }
            return mostFrequest;
        }
    }

  • 1
    C

    This will fail the following test:

    [4, 1, -1, 2, -1, 2, 3] 
    1
    

    Output: [-1,2]

    However, expected answer should be [-1] or [2].


  • 0

    Thank you @cooniur I will fix the solution and update the code.


  • 0

    I have tried submitting my solution again to leetcode OJ and it passed. I run the test cases you have suggested and it failed as expected. Thank you very much for pointing that out. I have submitted your suggestion as an additional test case to OJ and referenced you leetcode.com/library/application/707


  • 0

    I just had to change a way I retrieve the frequency. Instead of adding all values for a given frequency, I only add values up to k. Thank you very much once again. Below is the updated answer.

     public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer>result = new ArrayList<Integer>();
            
            // data sorting and filtering
            Map<Integer, Integer>mostFrequest = buildFreqMap(nums);
            TreeMap<Integer, List<Integer>>mostFrequestSorted = getSortedByValueMap(mostFrequest);
            // main logic
            for(Integer key : mostFrequestSorted.descendingKeySet()){
                List<Integer> freq = mostFrequestSorted.get(key);
                for(Integer val: freq){
                    if(result.size() >= k)
                        break;
                    result.add(val);
                }
            }
           // System.out.println(mostFrequestSorted.descendingMap());
            return result;
        }
        
        public static TreeMap<Integer, List<Integer>> getSortedByValueMap(final Map<Integer, Integer>mostFrequest){
            TreeMap<Integer, List<Integer>>mostFrequestSorted = new TreeMap<Integer, List<Integer>>();
            for(Map.Entry<Integer, Integer> entry : mostFrequest.entrySet()){
                if(mostFrequestSorted.get(entry.getValue()) == null)
                    mostFrequestSorted.put(entry.getValue(), new ArrayList<Integer>());
                
                mostFrequestSorted.get(entry.getValue()).add(entry.getKey());
            }
            return mostFrequestSorted;
        }
        
        public static Map<Integer, Integer> buildFreqMap(int[]nums){
            Map<Integer, Integer>mostFrequest = new HashMap<Integer, Integer>();
            
            for(int i = 0; i < nums.length; i++){
                if(mostFrequest.get(nums[i]) == null)
                    mostFrequest.put(nums[i], 1);
                else{
                    int val = mostFrequest.get(nums[i])+1;
                    mostFrequest.put(nums[i], val);
                }
            }
            return mostFrequest;
        }
    }
    

Log in to reply
 

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