java - 编程测试 - Codility - Dominator

Question

关闭。这个问题需要更多 focused .它目前不接受答案。

---

想要改进这个问题吗？ 更新问题，使其只关注一个问题 editing this post .

关闭3年前。

Improve this question

我刚刚遇到了一个编码问题，这让我很难过，我仍在努力弄清楚如何才能满足空间和时间复杂性限制。

问题如下:数组中的显性成员是占据数组中一半以上位置的成员，例如:

{3, 67, 23, 67, 67}

67 是主要成员，因为它出现在数组中的 3/5 (>50%) 位置。

现在，您应该提供一个方法，该方法接收一个数组，如果存在则返回主导成员的索引，如果不存在则返回 -1。

很简单，对吧？好吧，如果不是因为以下限制，我本来可以轻松解决问题的:

• 预计时间复杂度为 O(n)
• 预期空间复杂度为 O(1)

我可以看到你如何在 O(n) 时间和 O(n) 空间复杂度以及 O(n^2) 时间和 O(1) 空间复杂度下解决这个问题，但不是同时满足 O( n) 时间和 O(1) 空间。

我真的很高兴看到这个问题的解决方案。别担心，截止日期已经过了几个小时(我只有 30 分钟)，所以我不想作弊。谢谢。

Answer 1

用 Google 搜索“计算数组的主要成员”，它是 first result .请参阅第 3 页描述的算法。

element x;
int count ← 0;
For(i = 0 to n − 1) {
  if(count == 0) { x ← A[i]; count++; }
  else if (A[i] == x) count++;
  else count−−;
}
Check if x is dominant element by scanning array A

基本上观察到，如果在数组中找到两个不同的元素，则可以将它们都删除，而不会改变其余元素上的主导元素。这段代码只是不断抛出成对的不同元素，跟踪它看到单个剩余未配对元素的次数。