A solving function finding k majority elements may be helpful for future problems, O(k*n) time and O(k) space


  • 3
    Z

    Only post the function. It returns all elements occur more than (n/k) times. In this problem, k=3.
    The time complexity is O(k*n), and O(k) space. Also work for 'Majority Element'. And any future following problems.

    Usage in this problem: return solver(nums, 3);

    private List<Integer> solver(int[] nums, int k) {
            List<Integer> ret = new LinkedList<Integer>();
            int[] buffer = new int[k-1];
            int[] count = new int[k-1];
            Arrays.fill(count, 0);
            Arrays.fill(buffer, Integer.MIN_VALUE);
            for(int i=0;i<nums.length;i++) {
                boolean find = false;
                for(int j=0;j<k-1;j++) {
                    if(nums[i]==buffer[j]) {
                        count[j]++;
                        find=true;
                        break;
                    } 
                    else if(count[j]==0) {
                        buffer[j]=nums[i];
                        count[j]=1;
                        find=true;
                        break;
                    }
                }
                if(!find) {
                    for(int j=0;j<k-1;j++) {
                        count[j]--;
                    }
                }
            }
            Arrays.fill(count, 0);
            for(int i=0;i<nums.length;i++) {
                for(int j=0;j<k-1;j++) {
                    if(nums[i]==buffer[j]) {
                        count[j]++;
                        if(count[j]>(nums.length/k)) {
                            ret.add(nums[i]);
                            count[j]=Integer.MIN_VALUE;
                        }
                        break;
                    }
                }
            }
            return ret;
        }

  • 1
    L

    if you code will work for the case [1,2,2,3,2,3,1,3]? (k = 3)


  • 0
    Z

    Wrong answer...


Log in to reply
 

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