Randomized solution with O(1) space and linear time


  • 0
    Z

    If there is a number which frequency exceeds n/3 then randomly selecting a number from the array, the probability that we take that number is 33.33 %. It is high enough probability to apply randomized solution. Thus, we take k(int my case k = 10) random numbers from the array, then check only those numbers which frequency exceeds some predefined threshold through traversing the original array. It can be considered as constant space because k is very small in compare to the size of array, and it doesn't depend on input size.

    public class Solution {

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        
        if(nums.length == 0) return list;
        int n = nums.length;
        int rand[] = new int[10];
        for(int i = 0;i<10;i++){
            rand[i] = nums[(int)(Math.random()*n)];
        }
        
        
        List<Integer> check = new ArrayList<>();
        for(int i = 0;i<10;i++){
            int count = 1;
            for(int j = i+1;j<10;j++) {
                if(rand[i] == rand[j]) count++;
            }
            if(count >= 2) check.add(rand[i]);
        }
        
        for(int i = 0;i<check.size();i++){
            int count = 0;
            for(int j = 0;j<n;j++){
                if(nums[j] == check.get(i)) count++;
            }
            if(count > n/3) {
                if(!list.contains(check.get(i)))
                    list.add(check.get(i));
            }
        }
        return list;
    }
    

    }


Log in to reply
 

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