Python 中的多数元素
假设我们有一个整数数组。任务是在给定数组中找到特定元素的索引。例如,
输入1-
N = 8 A[ ] = { 1,2,4,3,3,1,1,5}
输出-
1
说明-在给定的整数数组中,出现最多的数字是“1”。因此输出为'1'。
输入2-
N = 6 A[ ] = {1,5,4,4,1,1}
输出-
1
说明-在给定的整数数组中,出现最多的数字是“1”。因此我们可以返回输出“1”。
解决这个问题的方法
给定的数组包含多个整数,我们必须在其中找到数组中出现频率最高的元素。为了在线性时间O(n)和线性空间中解决这个问题,O(n)我们可以使用哈希图的方法。
在这种方法中,我们将创建一个无序map(STLLibrary)的键值对组成,其中键是一个元素,值是元素的出现。在遍历映射时,我们将找到该数字的最大出现次数并将该数字作为输出返回。
输入一个大小为N的数组
整数函数maxOccurrence(intA[],intsize)将数组及其大小作为输入,并返回频率最高的数字。
通过将键作为元素和值作为其频率来创建数组所有元素的哈希图。
迭代映射并检查是否有任何频率最高的元素,然后将结果作为数字返回。否则,如果数组中不存在任何数字,则返回“-1”。
示例
def checkMajorityElement(arr, N): mp = {} for i in range(0, N): if arr[i] in mp.keys(): mp[arr[i]] += 1 else: mp[arr[i]] = 1 for key in mp: if mp[key] > (N / 2): return key return -1 print("输入数组的大小:") N = int(6) print("输入数组元素:") arr = [2,1,1,2,2,2] ans = checkMajorityElement(arr, N) if ans != -1: print("Majority Element is: %d" % ans) else: print("No majority element in array")输出结果
运行上面的代码将生成输出,
输入数组的大小: 6 输入数组元素: 2 1 1 2 2 2 Majority Element is: 2