当前位置 博文首页 > 是琳琳呀！的博客：剑指offer 第28题数组中有一个数字出现的次数
题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解析：
该题可以有多种方法进行解答：
1：借助HashMap
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<array.length;i++){
if(!map.containsKey(array[i])){
map.put(array[i],1);
}else{
int count=map.get(array[i]);
map.put(array[i],++count);
}
}
// 打印所有的键值对
// entrySet(): 将Map中的键值对放在Set中返回了
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(entry.getValue()>array.length/2){
return entry.getKey();
}
}
return 0;
}
}
2.使用排序Arrays.sort(array)；
数组中有一个数字出现的次数超过了数组长度的一半。如果我把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组一半的数字。也就是说，这个数字就是统计学上的中位数，即长度为n的数组中第n/2的数字。
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
Arrays.sort(array);
int count=0;
for(int i=0;i<array.length;i++){
//让每个数组元素与中间比较，因为如果元素个数
//大于数组的一半即中间元素一定为那个元素
if(array[i]==array[array.length/2]){
count++;
}
}
if(count>array.length/2){
return array[array.length/2];
}
return 0;
}
}
3:基于Partition函数算法
这种算法是受快速排序算法的启发。在随机快速排序算法中，我们现在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数。如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程.
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length<=0){
return 0;
}
partition(array,0,array.length-1);
int mid=array[array.length/2];
int count=0;
for(int i=0;i<array.length;i++){
if(array[i]==mid){
count++;
}
}
if(count<=array.length/2){
return 0;
}
return mid;
}
public void partition(int[] array,int start,int end){
if(start>=end){
return;
}
int ts=start;
int te=end;
int tmp=array[ts];
while(ts<te){
while(ts<te&&array[te]>=tmp){
te--;
}
array[ts]=array[te];
while(ts<te&&array[ts]<=tmp){
ts++;
}
array[te]=array[ts];
}
array[ts]=tmp;
partition(array,start,ts-1);
partition(array,ts+1,end);
}
}
4。摩尔选举法
候选人(cand_num)初始化为nums[0]，票数count初始化为1。
当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
当票数count为0时，更换候选人，并将票数count重置为1。
遍历完数组后，cand_num即为最终答案。
为何这行得通呢？
投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
且“多数元素”的个数> ? n/2 ?，其余元素的个数总和<= ? n/2 ?。
因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。
这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。
无论数组是1 2 1 2 1，亦或是1 2 2 1 1，总能得到正确的候选人。
public int majorityElement(int[] nums) {
if(nums==null||nums.length==0){
return -1;
}
int cnt=nums[0];
int count=1;
for(int i=1;i<nums.length;i++){
if(count==0){
cnt=nums[i];
}
if(cnt==nums[i]){
count++;
}else{
count--;
}
}
return cnt;
}
