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) 中解决此问题，我们可以使用哈希映射的方法。

在这种方法中，我们将创建一个无序映射（STL 库），其中包含键值对，其中键将是元素，值将是元素的出现次数。在遍历映射时，我们将找到数字的最大出现次数并返回该数字作为输出。

  • 输入大小为 N 的数组

  • 整数函数 maxOccurrence(int A[], int size) 以数组及其大小作为输入，并返回频率最高的数字。

  • 通过将键作为元素并将值作为其频率来创建数组所有元素的哈希映射。

  • 遍历映射并检查是否有任何元素具有最高频率，然后将结果作为数字返回。否则，如果数组中不存在任何数字，则返回“-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("Enter size of array:")
N = int(6)
print("Enter elements of array:")
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")

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

运行以上代码将生成以下输出：

Enter size of array: 6
Enter elements of array: 2 1 1 2 2 2
Majority Element is: 2

更新于：2021 年 2 月 5 日

2K+ 次查看

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告