二分之一

如果数组中保证有一个元素数目超过一半，那么对其进行计数，遍历到一个该元素则count++，否则--，那么最后遍历完成之后这个元素的count必然是正数。

现在问题在于，如何找这个计数的元素。其实上面我们已经知道了，在遍历结束以后count必然大于零。所以我们可以在遍历的过程当中进行更改，如果count<0则直接把元素更换为当前的元素。遍历结束以后被统计的元素就是我们想要的，超过一半的元素。

那么

def majority_elem(array):
count = 0
for i in array:
if count == 0:
majo_elem = i
count += 1
else:
if i == majo_elem:
count += 1
else:
count -= 1
return majo_elem
#a = [1,1,1,1,1,2,3,569,8,9,9,7,9,36,4,98,9,3,4,7,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]
#print(majorityElem(a))

时间复杂度为n，空间复杂度为1

如果不确定是否存在这样一个元素，则在上述操作之后，对返回的元素关于原先数组进行再一次遍历，确认其是否超过一半。

三分之一

首先一个数组中超过三分之一的元素可能有两个。这点需要注意。

然后参考上述代码即可。定义两个数，标记前两个元素，如果遍历中的元素是其中一个，则该元素++，另一个元素不变。

def majority_tri_elem(array):
count_m = 0
count_n = 0
m = 0
n = m
for num in array:
if (num != m):
n = num
else:
return m # The array has only one element m
for num in array:
if (count_m == 0 or num == m):
m = num
count_m += 1
if (count_n == 0 or num == n):
n = num
count_n += 1
else :
count_m -=1
count_n -=1
return (m,n)

这里务必要注意，除非明确知道数组中有两个次数大于三分之一的元素，否则必须对其带回进行遍历判断。如果只有一个元素大于三分之一，也需要对其进行判断。m和n的初值必须注意，m可以是第一个元素，n必须为不为m的元素。否则m和n必然是同一个

最后

以上就是温婉乌冬面为你收集整理的找出数组中出现次数超过一半的元素，找出数组中出现次数超过三分之一的元素二分之一三分之一的全部内容，希望文章能够帮你解决找出数组中出现次数超过一半的元素，找出数组中出现次数超过三分之一的元素二分之一三分之一所遇到的程序开发问题。

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