Java Generalized Solution For n /k majority


  • 0
    A
    // k = 3 for n/3, k = 2 for n/2 etc.
    public List<Integer> majorityElement(final int[] nums, final int k) {
            Map<Integer, Integer> numCountMap = new HashMap<>();
    
            for (int num : nums) {
                if (numCountMap.containsKey(num)) {
                    numCountMap.put(num, numCountMap.get(num)+1);
                } else if (numCountMap.size() < k-1) {
                    numCountMap.put(num, 1);
                } else {
                    Iterator<Map.Entry<Integer, Integer>> iterator = numCountMap.entrySet().iterator();
                    while (iterator.hasNext()) {
                        Map.Entry<Integer, Integer> entry = iterator.next();
                        int numKey = entry.getKey();
                        numCountMap.put(numKey, numCountMap.get(numKey)-1);
                        if (numCountMap.get(numKey) == 0) {
                            iterator.remove();
                        }
                    }
                }
            }
    
            numCountMap.entrySet().stream().forEach(entry -> entry.setValue(0));
            Arrays.stream(nums)
                    .forEach(num -> {
                        if (numCountMap.containsKey(num)) {
                            numCountMap.put(num, numCountMap.get(num) + 1);
                        }
                    });
    
            return numCountMap.entrySet().stream()
                    .filter(entry -> entry.getValue() > nums.length / k)
                    .map(entry -> entry.getKey())
                    .collect(Collectors.toList());
        }
    

Log in to reply
 

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