用分治法求解主元素问题（python）
用分治法求解主元素问题（python）
问题描述：
设 T [ 0 : n − 1 ] T[0:n-1] T[0:n−1]是n个元素的数组，如果其中某个元素x在整个数组中的出现次数超过n/2，则称x为数组 T T T的主元素。
代码：
def MajorElement(data):left_data = []right_data = []if len(data) == 1:return data[0]#求中间位置midindex = int(len(data)/2)#将data分为左右两部分 for i in range(len(data)):if i < midindex:left_data.append(data[i])else:right_data.append(data[i])#确定主元素majorelement1 = MajorElement(left_data)majorelement2 = MajorElement(right_data)if majorelement1==majorelement2:return majorelement1else:count1=0count2=0for i in range(len(data)):if data[i]==majorelement1:count1=count1+1if data[i]==majorelement2:count2=count2+1if count1>len(data)/2:return majorelement1if count2>len(data)/2:return majorelement2else:majorelement='null'return majorelement
测试代码1：
data=[1,2,3,4,5,8,6,4,7,3,9,5,5,5,5,5,5,5,5,5,5,5]
majorelement=MajorElement(data)
print(majorelement)
结果：
如果输入数据由文txt文件提供。文件的第1行为数组S中元素个数n；接下来的n 行中，每行有一个自然数。程序运行结束时，将计算结果输出到txt文件中。输出文件中包含问题的答案：找不到主元素时给出null，找到时给出主元素的值。
测试代码：
data = np.loadtxt("D:\Algorithm\input3.txt",int,encoding='utf-16')
print(data)
majorelement=MajorElement(data)
print(majorelement)
# 写入TXT文件中
with open("D:\Algorithm\input3.txt","a+",encoding='utf-16')as f:f.write('主元素是：')f.write(str(majorelement))
结果：
分析：
时间复杂性可由递推式表示： T ( n ) = 2 T ( n / 2 ) + O ( n ) T(n)=2T(n/2)+O(n) T(n)=2T(n/2)+O(n)，即 T ( n ) = O ( n l o g n ) T(n)=O(nlogn) T(n)=O(nlogn)
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！