[leetCode]169.多数元素

暴力法

两层循环通过遍历判断每个数字的出现次数是否大于floor

class Solution {
    public int majorityElement(int[] nums) {
        int floor = nums.length / 2;
        for(int i = 0; i < nums.length; i++){
            int count = 0;
            for(int j = 0; j < nums.length; j++){
                if(nums[i] == nums[j]){
                    ++count;
                }
            }
            if(count > floor) return nums[i];
        }
        return 0;
    }
}

哈希表

用哈希表记录对应元素与其出现的次数

class Solution {
    public int majorityElement(int[] nums) {
        int floor = nums.length/2;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(!map.keySet().contains(nums[i])){
                map.put(nums[i],1);
            }else {
                map.replace(nums[i], map.get(nums[i])+1);
            }  
        }
        for(int i = 0; i < nums.length; i++){
            if(map.get(nums[i])>floor) return nums[i];
        }
        return 0;
    }
}

```java
class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int ans = nums[0];
        int count = 1;
        for(int i = 0; i < nums.length; i++){
            if(!map.keySet().contains(nums[i])){
                map.put(nums[i],1);
            }else {
                map.replace(nums[i], map.get(nums[i])+1);
                if(map.get(nums[i])+1 > count){
                    count = map.get(nums[i])+1;
                    ans = nums[i];
                }
            }  
        }
        return ans;
    }
}

双指针

先排序，再利用双指针计数

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length == 1)return nums[0];
        int floor = nums.length/2;
        Arrays.sort(nums);
        int ans = 0;
        int count = 0;
        int i = 0;
        for(int j = i + 1; j < nums.length; j++){
            if(nums[i] != nums[j] && j-i>count) {
                count = j-i;
                ans = nums[i]; 
                i = j;
            }
            if(j == nums.length-1 && j-i+1 > count){
                ans = nums[i]; 
            }
        }
        return ans;
    }
}

排序

众数肯定大于数组的一半，所以对数组排序，返回中间值即可

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

随机化

众数占多数，通过随机选取一个数字，判断该数是否为众数。如果是则退出

class Solution {

    public int randIndex(Random rand, int min, int max){
        return rand.nextInt(max - min) + min;
    }

    public int countOccurence(int x, int[] nums){
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == x) ++count;
        }
        return count;
    }

    public int majorityElement(int[] nums) {
        Random rand = new Random();
        while(true){
            int current = nums[randIndex(rand, 0, nums.length)];
            if(countOccurence(current, nums) > nums.length /2){
                return current;
            }
        }
    }
}

分治

如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。

class Solution {

    public int countInRange(int x,int[] nums ,int lo, int hi){
        int count = 0;
        for(int i = lo; i <= hi; i++){
            if(nums[i] == x) ++count;
        }
        return count;
    }

    public int majorityElementRec(int[] nums, int lo, int hi){
        if(lo == hi) return nums[lo];
        int mid = lo + (hi - lo)/2;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums,mid+1,hi);
        if(left == right) return left;

        if(countInRange(left,nums,lo,hi) > countInRange(right,nums,lo,hi)){
            return left;
        }else{
            return right;
        }
    }

    public int majorityElement(int[] nums) {
       return majorityElementRec(nums, 0, nums.length -1);
    }
}

Boyer-Moore 投票算法

传送门

class Solution {
    public int majorityElement(int[] nums) {
       int count = 0;
       Integer candidate = null;
       for(int num :nums){
           if(count == 0) {
               candidate = num;
           }
           count += (num == candidate) ? 1 : -1;
       }
       return candidate;
    }
}

随机切分

在数组中随机选取一个元素作为切分元素进行切分，并返回下标。由于含有多数元素的数组排序后数组的中间元素就为多数元素，所以

• 如果切分元素下标等于num.length/2则该元素就为多数元素；
• 如果切分元素下标小于num.length/2则对该元素右边继续切分；
• 如果切分元素下标大于num.length/2则对该元素左边继续切分；

class Solution {
    public int majorityElement(int[] nums) {
       if(nums == null || nums.length == 0) return 0;
       int lo = 0;
       int hi = nums.length - 1;
       int middle = nums.length >> 1;
       int index = partition(nums, lo, hi);
       while(index != middle){
           if(index > middle){
               hi = index - 1;
               index = partition(nums, lo, hi);
           }else if(index < middle){
               lo = index + 1;
               index = partition(nums, lo, hi);
           }
       }
       return nums[middle];
    }

     /**
    *   随机切分函数
    */
    private int partition(int[] a, int lo, int hi){
        if(a == null || a.length == 0 || lo < 0 || hi > a.length)
            throw new RuntimeException("Invalid Parameters");
        int index = randRange(new Random(), lo, hi+1);
        exch(a, hi, index);
        int small = lo - 1;
        for(index = lo; index < hi; ++index){
            if(a[index] < a[hi] ){
                ++small;
                if(index != small){
                    exch(a, small, index);
                }
            }
        }
        small++;
        exch(a, small, hi);
        return small;
    }

    private int randRange(Random rand, int min, int max) {
        if(max - min == 0) return min;
        int r = rand.nextInt(max - min) + min;
        return r;
    }

    private void exch(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}