死磕算法系列文章
“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 的众数为x,数组长度为n。
推论一: 若记众数的票数为+1,非众数的票数为-1,则一定有所有数字的票数和> 0。推论二: 若数组的前a个数字的票数和=0,则数组剩余(n-a)个数字的票数和一定仍> 0,即后(n- a)个数字的众数仍为x。
根据以上推论,记数组首个元素为n1,众数为x,遍历并统计票数。当发生票数和= 0时,剩余数组的众 数-定不变,这是由于:
利用此特性,每轮假设发生票数和 = 0 都可以 缩小剩余数组区间 。当遍历完成时,最后一轮假设的数字即为众数。
算法流程:
votes = 0
, 众数 x
;nums
中的每个数字 num
;votes
等于 0 ,则假设当前数字 num
是众数;num = x
时,票数 votes
自增 1 ;当 num != x
时,票数 votes
自减 1 ;x
即可;复杂度分析:
nums
长度。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/