gpt4 book ai didi

arrays - 查找数组中的多数元素

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:12:41 26 4
gpt4 key购买 nike

多数元素是出现超过数组大小一半的元素。

如何在 O(n) 中找到数组中的多数元素?

示例输入:

{2,1,2,3,4,2,1,2,2}

预期输出:

2

最佳答案

// returns -1 if there is no element that is the majority element, otherwise that element

// funda :: if there is a majority element in an array, say x, then it is okay to discard
// a part of that array that has no majority element, the remaining array will still have
// x as the majority element

// worst case complexity : O(n)

int findMajorityElement(int* arr, int size) {
int count = 0, i, majorityElement;
for (i = 0; i < size; i++) {
if (count == 0)
majorityElement = arr[i];
if (arr[i] == majorityElement)
count++;
else
count--;
}
count = 0;
for (i = 0; i < size; i++)
if (arr[i] == majorityElement)
count++;
if (count > size/2)
return majorityElement;
return -1;
}

关于arrays - 查找数组中的多数元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4325200/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com