[[439477]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員千羽」，作者程序員千羽 。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員千羽公眾號(hào)。

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

數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

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

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

解題思路：

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

本題常見的三種解法:

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

摩爾投票法：

“設(shè)輸入數(shù)組 nums 的眾數(shù)為x，數(shù)組長度為n。

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

根據(jù)以上推論,記數(shù)組首個(gè)元素為n1，眾數(shù)為x，遍歷并統(tǒng)計(jì)票數(shù)。當(dāng)發(fā)生票數(shù)和= 0時(shí)，剩余數(shù)組的眾 數(shù)-定不變，這是由于:

• 當(dāng)n1=x：抵消的所有數(shù)字中，有一半是眾數(shù)x。
• 當(dāng)n1≠x：抵消的所有數(shù)字中，眾數(shù)x的數(shù)量最少為0個(gè)，最多為一半。

利用此特性，每輪假設(shè)發(fā)生票數(shù)和 = 0 都可以 縮小剩余數(shù)組區(qū)間 。當(dāng)遍歷完成時(shí)，最后一輪假設(shè)的數(shù)字即為眾數(shù)。

算法流程:

• 初始化： 票數(shù)統(tǒng)計(jì) votes = 0 ， 眾數(shù) x;
• 循環(huán)： 遍歷數(shù)組 nums 中的每個(gè)數(shù)字 num ;
  • 當(dāng) 票數(shù) votes 等于 0 ，則假設(shè)當(dāng)前數(shù)字 num 是眾數(shù);
  • 當(dāng) num = x 時(shí)，票數(shù) votes 自增 1 ;當(dāng) num != x 時(shí)，票數(shù) votes 自減 1 ;
• 返回值： 返回 x 即可;

復(fù)雜度分析：

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

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; 
    } 

拓展： 由于題目說明 給定的數(shù)組總是存在多數(shù)元素 ，因此本題不用考慮 數(shù)組不存在眾數(shù) 的情況。若考慮，需要加入一個(gè) “驗(yàn)證環(huán)節(jié)” ，遍歷數(shù)組 nums 統(tǒng)計(jì) x 的數(shù)量。

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

時(shí)間和空間復(fù)雜度不變，仍為 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; 
        } 
        // 驗(yàn)證 x 是否為眾數(shù) 
        for(int num : nums) 
            if(num == x) count++; 
        return count > nums.length / 2 ? x : 0; // 當(dāng)無眾數(shù)時(shí)返回 0 
    } 

代碼

package com.nateshao.sword_offer.topic_31_majorityElement; 
 
import java.util.Arrays; 
 
/** 
 * @date Created by 邵桐杰 on 2021/12/5 17:16 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 劍指 Offer 39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字 
 * 題目描述：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請(qǐng)找出這個(gè)數(shù) 
 * 字。如果不存在則輸出 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; 
        } 
        // 驗(yàn)證 x 是否為眾數(shù) 
        for(int num : nums) 
            if(num == x) count++; 
        return count > nums.length / 2 ? x : 0; // 當(dāng)無眾數(shù)時(shí)返回 0 
    } 
    /****************** 劍指offer **********************/ 
    /** 
     * 思路：將首次出現(xiàn)的數(shù) count+1，與之后的數(shù)進(jìn)行比較，相等則+1，否則—1， 
     * 最后進(jìn)行校驗(yàn)是否超過長度的一半。 
     * 
     * @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]; 
    } 
} 

 參考文獻(xiàn)：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/