數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
本文轉(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ù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。難度：簡(jiǎn)單示例:
- 輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
- 輸出: 2
解題思路：
“本文將 “數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字” 簡(jiǎn)稱為 “眾數(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ù)組長(zhǎng)度為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 長(zhǎng)度。
- 空間復(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ù)組長(zhǎng)度一半，則返回 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ù)組長(zhǎng)度的一半，請(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)是否超過長(zhǎng)度的一半。
- *
- * @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/
