169多數元素

​​​​​​多數元素

給定一個大小為 n 的數組 nums ，傳回其中的多數元素。多數元素是指在數組中出現次數 大于 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，并且給定的數組總是存在多數元素。

 JAVA(練習快排):

class Solution {
    public int majorityElement(int[] nums) {
        //Arrays.sort(nums);
        QuickSort(nums,0,nums.length-1);
        int max=1,cnt=0;
        for(int i=1;i<nums.length;i++){
            if(nums[i-1]==nums[i]){
                max++;
                cnt=Math.max(max,cnt);
                if(cnt>nums.length/2) 
                    return nums[i];
            }else{
                max=1;
            }
        }
        return nums[0];
    }
    
    public void QuickSort(int[] nums,int low,int high){
        if(low<high){
            int pivotpos=Partition(nums,low,high);
            QuickSort(nums,low,pivotpos-1);
            QuickSort(nums,pivotpos+1,high);
        }
    }
    public int Partition(int[] nums,int low,int high){
        int pivot=nums[low];
        while(low<high){
           while(low<high&&nums[high]>=pivot) --high;
            nums[low]=nums[high];
            while(low<high&&nums[low]<=pivot) ++low;
            nums[high]=nums[low]; 
        }
        nums[low]=pivot;
        return low;
    }
}
           

JAVA:

注：題目規定總存在多數元素，即當cnt不為0時，對應的元素即為多數元素。

時間複雜度O(n)

class Solution {
    public int majorityElement(int[] nums) {     
        int res=nums[0],cnt=0;
        for(int num:nums){
            if(cnt==0){
                res=num;
                cnt=1;
            }else{
                if(num==res){
                    cnt++;
                }else{
                    cnt--;
                }
            }  
        }
        return res;
    }
}