[[439477]]

本文轉載自微信公眾號「程序員千羽」，作者程序員千羽 。轉載本文請聯系程序員千羽公眾號。

Leetcode : https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_31_majorityElement/Solution.java

數組中出現次數超過一半的數字

“題目描述 ：數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。你可以假設數組是非空的，并且給定的數組總是存在多數元素。難度：簡單示例:

輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 
 
輸出: 2 

解題思路：

“本文將 “數組中出現次數超過一半的數字” 簡稱為 “眾數” 。需要注意的是，數學中眾數的定義為 “數組中出現次數最多的數字” ，與本文定義不同。

本題常見的三種解法:

• 哈希表統計法：遍歷數組 nums ，用HashMap統計各數字的數量，即可找出眾數。此方法時間和空間復雜度均為O(N)。
• 數組排序法：將數組nums 排序,數組中點的元素一定為眾數。
• 摩爾投票法：核心理念為票數正負抵消。此方法時間和空間復雜度分別為O(N)和0(1)，為本題的 最佳解法。

摩爾投票法：

“設輸入數組 nums 的眾數為x，數組長度為n。

推論一： 若記眾數的票數為+1，非眾數的票數為-1,則一定有所有數字的票數和> 0。推論二： 若數組的前a個數字的票數和=0，則數組剩余(n-a)個數字的票數和一定仍> 0，即后(n- a)個數字的眾數仍為x。

根據以上推論,記數組首個元素為n1，眾數為x，遍歷并統計票數。當發生票數和= 0時，剩余數組的眾 數-定不變，這是由于:

• 當n1=x：抵消的所有數字中，有一半是眾數x。
• 當n1≠x：抵消的所有數字中，眾數x的數量最少為0個，最多為一半。

利用此特性，每輪假設發生票數和 = 0 都可以 縮小剩余數組區間 。當遍歷完成時，最后一輪假設的數字即為眾數。

算法流程:

• 初始化： 票數統計 votes = 0 ， 眾數 x;
• 循環： 遍歷數組 nums 中的每個數字 num ;
  • 當 票數 votes 等于 0 ，則假設當前數字 num 是眾數;
  • 當 num = x 時，票數 votes 自增 1 ;當 num != x 時，票數 votes 自減 1 ;
• 返回值： 返回 x 即可;

復雜度分析：

• 時間復雜度 O(N) ： N 為數組 nums 長度。
• 空間復雜度 O(1) ： votes 變量使用常數大小的額外空間。

public static int majorityElement1(int[] nums) { 
        int x = 0, votes = 0; 
        for(int num : nums){ 
            if(votes == 0) x = num; 
            votes += num == x ? 1 : -1;// votes = votes + ( num == x ? 1 : -1); 
        } 
        return x; 
    } 

拓展： 由于題目說明 給定的數組總是存在多數元素 ，因此本題不用考慮 數組不存在眾數 的情況。若考慮，需要加入一個 “驗證環節” ，遍歷數組 nums 統計 x 的數量。

• 若 x 的數量超過數組長度一半，則返回 x ;
• 否則，返回未找到眾數;

時間和空間復雜度不變，仍為 O(N)和 O(1) 。

public int majorityElement11(int[] nums) { 
        int x = 0, votes = 0, count = 0; 
        for(int num : nums){ 
            if(votes == 0) x = num; 
            votes += num == x ? 1 : -1; 
        } 
        // 驗證 x 是否為眾數 
        for(int num : nums) 
            if(num == x) count++; 
        return count > nums.length / 2 ? x : 0; // 當無眾數時返回 0 
    } 

代碼

package com.nateshao.sword_offer.topic_31_majorityElement; 
 
import java.util.Arrays; 
 
/** 
 * @date Created by 邵桐杰 on 2021/12/5 17:16 
 * @微信公眾號 程序員千羽 
 * @個人網站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 劍指 Offer 39. 數組中出現次數超過一半的數字 
 * 題目描述：數組中有一個數字出現的次數超過數組長度的一半，請找出這個數 
 * 字。如果不存在則輸出 0。 
 */ 
public class Solution { 
    public static void main(String[] args) { 
        int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2}; 
        int i1 = majorityElement1(arr); 
        int i2 = majorityElement2(arr); 
        int i3 = majorityElement3(arr); 
        System.out.println("i = " + i1); // i = 2 
        System.out.println("i2 = " + i2); 
        System.out.println("i3 = " + i3); 
 
    } 
    /******************** 精選 *********************/ 
    public static int majorityElement1(int[] nums) { 
        int x = 0, votes = 0; 
        for(int num : nums){ 
            if(votes == 0) x = num; 
            votes += num == x ? 1 : -1;// votes = votes + ( num == x ? 1 : -1); 
        } 
        return x; 
    } 
    /**************** 拓展 *********************/ 
    public int majorityElement11(int[] nums) { 
        int x = 0, votes = 0, count = 0; 
        for(int num : nums){ 
            if(votes == 0) x = num; 
            votes += num == x ? 1 : -1; 
        } 
        // 驗證 x 是否為眾數 
        for(int num : nums) 
            if(num == x) count++; 
        return count > nums.length / 2 ? x : 0; // 當無眾數時返回 0 
    } 
    /****************** 劍指offer **********************/ 
    /** 
     * 思路：將首次出現的數 count+1，與之后的數進行比較，相等則+1，否則—1， 
     * 最后進行校驗是否超過長度的一半。 
     * 
     * @param nums 
     * @return 
     */ 
    public static int majorityElement2(int[] nums) { 
        int count = 0; 
        int candidate = 0; 
        for (int num : nums) { 
            if (count == 0) candidate = num; 
            count += (num == candidate) ? 1 : -1; 
        } 
        return checkMoreThanHalf(nums, candidate) ? candidate : 0; 
    } 
 
    private static boolean checkMoreThanHalf(int[] array, int number) { 
        int times = 0; 
        for (int i : array) { 
            if (i == number) times++; 
        } 
        return times * 2 >= array.length; 
    } 
 
 
    public static int majorityElement3(int[] nums) { 
        Arrays.sort(nums); 
        return nums[nums.length/2]; 
    } 
} 

 參考文獻：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/