现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数...

现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数。

方法1：Hash链表

方法2：使用两个变量A和B，其中A存储某个数组中的数，B用来计数。开始时将B初始化为0。

遍历数组，

如果B=0，则令A等于当前数，令B等于1；

如果当前数与A相同，则B=B+1；

如果当前数与A不同，则令B=B-1。

遍历结束时，A中的数就是要找的数。

这个算法的时间复杂度是O(n)，空间复杂度为O(1)。

c语言描述：

 

int main() {int i,A,B;int a[10]={1,2,3,1,2,1,1,6,1,1};A=a[5];B=0; 　　for(i=0; i<10; i++) 　　if(B=0){A = a[i];B =1;}elseif( A==a[i])B++;elseif(A!=a[i])B--;printf("%d", A);getchar(); 　　return 0; }

 

转载于:https://www.cnblogs.com/ciangcic/p/3528218.html

总结

以上是生活随笔为你收集整理的现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。