JAVA Random algorithm in 5ms


  • 1
    M
    public class Solution {
        public List<Integer> majorityElement(int[] nums) {
    
            List<Integer> l1=new ArrayList<>();
            HashSet<Integer> map=new HashSet<>();
            if(nums.length==0)
                return  l1;
            for (int i=0;i<10;i++)//you could change 10 to a larger number to avoid get wrong answer
            {
                int v1=((int)(Math.random()*nums.length*10))%nums.length;
                if(map.contains(nums[v1])==false&& isMajor(nums,nums[v1]))
                {
                    map.add(nums[v1]);
                    l1.add(nums[v1]);
                }
            }
            return  l1;
        }
    
        public  boolean isMajor(int[] nums,int v)
        {
            int n=0;
            for (int i=0;i<nums.length;i++)
            {
                if(nums[i]==v)
                    n++;
            }
            return  n>nums.length/3;
        }
    }

  • 0
    L
    This post is deleted!

  • 0

    Just wondering, the problem says O(1) space, but HashSet is used


Log in to reply
 

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