【剑指 offer】数组中出现次数超过一半的数字
✨个人主页:bit me👇
✨当前专栏:算法训练营👇
数 组 中 出 现 次 数 超 过 一 半 的 数 字
核心考点: 数组使用,简单算法的设计 |
描述:
给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。
数据范围:n ≤ 50000,数组中元素的值 0 ≤ val ≤ 10000
要求:空间复杂度:O(1),时间复杂度 : O(n)
输入描述:
保证数组输入非空,且保证有解
示例1:
输入:[1,2,3,2,2,2,5,4,2]
返回值:2
示例2
输入:[3,3,3,3,2,2,2]
返回值:3
示例3
输入:[1]
返回值:1
思路:
- 方法一:定义map,使用<数字,次数>的映射关系,最后统计每个字符出现的次数
- 方法二:排序,出现次数最多的数字,一定在中间位置。然后检测中间出现的数字出现的次数是否符合要求
- 方法三:目标条件:目标数据超过数组长度的一半,那么对数组,我们同时去掉两个不同的数字,到最后剩下的一个数就是该数字。如果剩下两个,那么这两个也是一样的,就是结果),在其基础上把最后剩下的一个数字或者两个回到原来数组中,将数组遍历一遍统计一下数字出现次数进行最终判断。
方法一:
import java.util.Map;
import java.util.HashMap;public class Solution {public int MoreThanHalfNum_Solution(int [] array) {if(array == null){return 0;}Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < array.length; i++){if(map.containsKey(array[i])){int count = map.get(array[i]);count++;map.put(array[i], count);}else{map.put(array[i], 1);}if(map.get(array[i]) > array.length / 2){return array[i];}}return 0;}
}
方法二:
import java.util.Arrays;
public class Solution {public int MoreThanHalfNum_Solution(int [] array) {if(array == null){return 0;}Arrays.sort(array);int target = array[array.length/2];int count = 0;for(int i = 0; i < array.length; i++){if(target == array[i]){count++;}}if(count > array.length/2){return target;}return 0;}
}
方法三:
public class Solution {public int MoreThanHalfNum_Solution(int [] array) {if(array == null){return 0;}int target = array[0];int times = 1;for(int i = 1; i < array.length; i++){if(times == 0){target = array[i];times = 1;}else if(array[i] == target){times++;}else{times--;}}times = 0;for(int i = 0; i < array.length; i++){if(target == array[i]){times++;}}return times > array.length/2 ? target : 0;}
}