数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
思路:思路有2:
其一,首先对数组进行排序,然后再利用动态规划解决问题;
其二,直接利用摩尔投票法进行问题的解决。
具体解法见下:
way1:
import java.util.Arrays;
import java.util.HashMap;
/*
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
思路:因为只有一个数字出现的次数大于数组的一半,那么就可以直接将整个数组中出现最多的这个数给找出来,
如出现的次数大于数组长度的一半,返回该数字。反之,返回0即可。
具体思路:先排序数组,然后利用动态规划的思想
*/
public class item26 {
public static int MoreThanHalfNum_Solution(int [] array) {
if(array.length==0){
return 0;
}
if(array.length==1){
return array[0];
}
int dp[] = new int[array.length];//dp[i]为插入第i个数字之后第i个数字出现的频率;
Arrays.sort(array);
dp[0]= 1;
int sum=0;
int maxindex=0;
for(int i=1;isum){
sum=dp[i];
maxindex=i;
}
}
if(sum>array.length/2){
//System.out.println(sum);
return array[maxindex];
}
else {
return 0;
}
}
}
way2:
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
}
第二种思想应该着重记一下,蛮有趣的~ 与君共勉!
Sirius_7 原创文章 37获赞 1访问量 432 关注 私信 展开阅读全文