剑指 Offer 39. 数组中出现次数超过一半的数字

快来打我* 2022-10-29 02:00 138阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[分治题解][Link 1]

//解法一:分治 不是很快  60%
    class Solution {
        
      public int majorityElement(int[] nums) {
        
    
    		return findMode(nums, 0, nums.length - 1);
    	}
    
    	private int findMode(int nums[], int leftIndex, int rightIndex) {
        
    
    		if (leftIndex == rightIndex) {
        
    			return nums[leftIndex];
    		}
    
    		int mid = (rightIndex + leftIndex) / 2;
    
    		int leftMode = findMode(nums, leftIndex, mid);
    		int rightMode = findMode(nums, mid + 1, rightIndex);
    
    		if (leftMode == rightMode) {
        
    			return leftMode;
    		}
    
    		// 两个子数组的众数不同，则遍历父数组，找出哪个众数更多
    
    		int leftModeCount = 0;
    		int rightModeCount = 0;
    
    		for (int i = leftIndex; i <= rightIndex; i++) {
        
    			if (nums[i] == leftMode) {
        
    				leftModeCount++;
    			}
    
    			if (nums[i] == rightMode) {
        
    				rightModeCount++;
    			}
    		}
    
    		return leftModeCount > rightModeCount ? leftMode : rightMode;
    	}
    }

//解法二：摩尔投票法 100%
    class Solution {
        
        public int majorityElement(int[] nums) {
        
            int res = 0;
            int votes = 0;
            for(int num : nums){
        
                if(votes == 0) res = num;
                votes += (num == res ? 1 : -1);
            }
            return res;
        }
    }

//解法三：位运算 30% 慢
    class Solution {
        
     public int majorityElement(int[] nums) {
        
            int result = 0, k = nums.length >> 1;
            for (int j = 0; j < 32; j++) {
        
                int count = 0;
                for (int num : nums) {
        
                    count += num >> j & 1;
                    if (count > k) {
        
                        result += 1 << j;
                        break;
                    }
                }
            }
            return result;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/5dd6cfa8530540579994293d621edf68.png
[Link 1]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/shu-zu-zhong-shu-de-ji-suan-by-fte/