找出数组中出现次数超过数组长度一半（>=1/2 >1/3）的那个数

先讨论超过数组长度一半的情况

超过数组长度一半意味着这个数字的个数大于其他全部数字个数之和，算法大致为，首先设置两个参数currentAxis,currentNum。参数currentAxis用来记录当前认为是我们要找的那个数字，参数currentNum用来记录CurrentAxis参数对应的那个数字连续出现的次数。步骤如下：

（1）初始化：设当前的数组为data[]，数组的长度为n。currentAxis=data[0]，currentNum=1；

（2）设i=1，遍历数组，转向（3）；

（3）当data[i]==currentAxis时，currentNum++，转向（5）；否则转向（4）；

（4）currentNum--，当CurrentNum==0时，currentAxis=data[i];

（5）当i==data.length时，转向（6）；否则，i++，转向（3）；

（6）输出currentAxis

为什么这个算法有效了，假设数组长为10，其中1的个数为6.即6/10，从数组第一个数开始，遇到不相同的数，则跳过这两个数，跳过的两个数可能有一个为1，或者一个都没有，这样的话 概率为5/8或者6/8，依然大于1/2,一直循环 最后一个肯定是我们要找的数。

int funtion(int data[], int length){
int currentAxis;
int currentNum=0;
for(int i=0;i<length;i++){
if(currentNum==0){
currentAxis=data[i];
currentNum=1;
}
else{
if(currentAxis==data[i])
currentNum++;
else
currentNum--;
}
}
return currentAxis;
}

接着是>1/3的情况，思想跟>1/2还是一样的，1/2的时候如果两个数字不相同，则可以跳过这2个数，剩下的数中还是满足大于1/2的情况。1/3的时候假设3个都不相同，则可以跳过3个数，剩下的树中还是满足大于1/3的情况。

代码的步骤如下：

（1）初始化：设当前的数组为data[]，数组的长度为n。currentAxis1=data[0]，currentNum1=1，               currentAxis2为空，currentNum2=0；

（2）设i=1，遍历数组，转向（3）；

（3）当data[i]==currentAxis1或者currentAxis2时，对应的currentNum++，转向（5）；否则转向（4）；

（4）currentNum1-- currentNum2--，当CurrentNum1或者currentAxis1或者currentAxis2==0时，对应的currentAxis=data[i];

（5）当i==data.length时，转向（6）；否则，i++，转向（3）；

（6）输出currentAxis1，currentAxis2

步骤6的输出就是待选的两个值，最后以这两个值为基础，遍历数组就可以找出最终究竟那个大于1/3

先是这样了，不知道对不对。写个代码试试去

最后

以上就是傻傻冷风为你收集整理的找出数组中出现次数超过数组长度一半（>=1/2 >1/3）的那个数的全部内容，希望文章能够帮你解决找出数组中出现次数超过数组长度一半（>=1/2 >1/3）的那个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。