Short Java, generalizes with O(N) time and O(k) space


  • 0

    I felt like torturing myself, so I rewrote my Python 6/7-liner in Java. If you want an explanation, please look there. Compared to Python it's awfully long and complicated, but for a Java solution I think it's fairly short. To generalize for the problem of searching elements appearing more than ⌊N/k⌋ times, just replace 3 by k.

    public List<Integer> majorityElement(int[] nums) {
        HashMap<Integer,Integer> ctr = new HashMap();
        
        // Find up to two candidates
        for (int n : nums) {
            ctr.put(n, ctr.getOrDefault(n, 0) + 1);
            if (ctr.size() == 3)
                for (int c : new HashSet<Integer>(ctr.keySet()))
                    if (ctr.get(c) == 1)
                        ctr.remove(c);
                    else
                        ctr.put(c, ctr.get(c) - 1);
        }
        
        // Count the votes for the candidates
        for (int c : ctr.keySet())
            ctr.put(c, 0);
        for (int n : nums)
            if (ctr.containsKey(n))
                ctr.put(n, ctr.get(n) + 1);
        
        // Determine the actual winners
        return ctr.keySet().stream()
                  .filter(c -> ctr.get(c) > nums.length / 3)
                  .collect(Collectors.toList());
    }

  • 0
    J

    I was writing some generalized solution as well, when I realized... if we are going to use a map anyway... why don't we just store all elements and count them? It will be almost same time/space complexity, right?


  • 0

    Similar, but O(N) space instead of O(k) space. And presumably k is (much) smaller than N.


Log in to reply
 

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