问题:
给定一个大小为N的数组,找到多数元素。多数元素是出现在地板(N/2)次以上的元素。您可以假设数组是非空的,并且多数元素始终存在于数组中。
我的答案:
function majorityElement($a){
$arr = array_count_values($a);
$newArr = array_flip($arr);
return $newArr[max($arr)];
}
链接到页面以供参考:
https://leetcode.com/problems/majority-element/
https://www.interviewbit.com/problems/majority-element/
为什么我的答案不正确?谢谢
我接触到的唯一面试问题是Stack Overflow问题。我不知道这个任务的设计者在想什么——当然,在Stack Overflow上推测其他开发人员为什么要做他们所做的事情是不合适的
我想说,如果我要接受这个挑战,我会努力通过在确定多数数后立即实现有条件的提前返回来将时间复杂性降至最低。
此代码段不需要在数据集上迭代多次。
代码:(演示)
class Solution {
/**
* @param Integer[] $nums
* @return Integer
* @throws Exception
*/
function majorityElement(array $nums): int
{
$majorityPoint = intdiv(count($nums), 2);
foreach ($nums as $num) {
$result[$num] = ($result[$num] ?? 0) + 1;
if ($result[$num] > $majorityPoint) {
return $num;
}
}
throw new Exception('No majority number in data set');
}
}