2 version solution in java, O(n) and O(nlogn)


  • 0
    N

    version 1. O(n) time

    用hashtabe, key為數字, value為該數字出現次數,
    並記錄最大次數, 時間為O(n)

     public int majorityElement(int[] nums) {
        
        Map<Integer,Integer> timesOf= new HashMap<>();
        
        int max = 0; 
        int ans = 0;
        
        for(int n: nums){
            
            if (timesOf.containsKey(n)){
                int times = timesOf.get(n)+1;
                timesOf.put(n, times);
            }else
                timesOf.put(n, 1);
            
            if(timesOf.get(n)>max){
                max = timesOf.get(n);
                ans = n;
            }
        }
        
        return ans;
    }
    

    version 2. O(nlogn) time, but more cleary

    因為最大次數數字出現了 ⌊ n/2 ⌋ 次, 因此只要排序後, 第 ⌊ n/2 ⌋ 個數字一定是最大次數數字

     public int majorityElement(int[] nums) {
        
        Arrays.sort(nums);
        int len = nums.length;
        return nums[ len/2 ];
    }

  • 0
    Z

    The second code is wrong, imagine:
    1112223333


  • 0
    J
    This post is deleted!

Log in to reply
 

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