2

上周我出现在一个采访中。我被问到以下问题：

给定一个包含 2n 个元素的数组，其中 n 个元素是相同的，其余的都是不同的。找出重复 n 次的元素。

元素的范围没有限制。

有人可以给我一个有效的算法来解决这个问题吗？

4

7 回答 7

7

“给定2n个元素的数组，其中n个元素相同，其余的都不同。找到重复n次的元素。”

这可以使用以下算法在 O(n) 中完成：

1) 遍历数组，检查元素 [i] 和 [i+1] 是否相同。

2) 遍历数组，检查元素 [i] 和 [i+2] 是否相同。

3) 如果 n = 2（因此长度 = 4），检查 0 和 3 是否相同。

解释：

称匹配元素 m 和不匹配元素 r。

对于 n = 2，我们可以构造 mmrr、mrmr 和 mrrm - 所以我们必须检查间隙大小 0、1 以及唯一可以有间隙大小 2 的地方。

对于 n > 2，我们不能构造没有大小为 0 或 1 的间隙的数组。例如，对于 n = 3，您必须像这样开始：mrrmr...但是您必须放置一个 m。类似地，对于 n = 4，mrrmrrmm - 没有大小为 0 或 1 的间隙将要求 ms 随着 n 的增加越来越多地超过 rs。证明这一点很容易。

于 2013-06-01T12:23:10.880 回答
3

You just need to find two elements that are the same.

One idea would be:

Get one element from the 2n elements.
If it is not in the a Set, put it in.
Repeat until you find one that is in that set.

于 2013-06-01T12:08:45.213 回答
1

好吧，如果复杂性无关紧要，一种天真的方法是使用两个循环，这是最坏的情况 O(n^2)。

for(int i = 0; i < array.size(); i++){
    for(int j = i + 1; j < array.size(); j++){
        if(array[i] == array[j]){
           // element found
    }
}
于 2013-06-01T12:18:13.340 回答
1

如果前四个元素都是不同的，则数组必须包含一对连续的目标元素...

int find(int A[n])
{
    // check first four elements (10 iterations = O(1))
    for (int i = 0; i < 4; i++)
       for (int j = i+1; j < 4; j++)
          if (A[i] == A[j])
              return A[i];

    // find the consecutive pair (n-4 iterations = O(n))
    for (int i = 3; i < n-1; i++)
        if (A[i] == A[i+1])
            return A[i];

    // unreachable if input matches preconditions
    throw invald_input;
}

这是最佳的 O(n) 时间，单次通过和 O(1) 空间。

于 2013-06-16T04:02:03.043 回答
0

我认为问题应该是“找到至少出现 n+1 次的元素”，如果它只出现 n 次，它们可以是两个。

假设输入中有这样的元素，可以使用以下算法。

input array of 2*n elements;

int candidate = input[0];
int count = 1;

for (int i = 1; i < 2*n; ++i) {
    if (input[i] == candidate) {
         count++;
    } else {
         count --;
         if (count == 0) candidate = input[i];
    }
}

return candidate;

如果请求是要查找是否存在 n+1 次元素，则需要再次遍历以查找在上一步找到的元素是否出现 n+1 次。

编辑：

有人建议，具有相同值的 n 个元素是连续的。如果是这种情况，只需使用上述算法并在计数达到 n 时停止。

于 2013-06-03T11:46:17.400 回答
0

If you find one element twice, that is the element as the questions says : Array of 2n elements is given, and out of this n elements are same, and remaining are all different. Find the element that repeats n time.

于 2013-06-01T12:08:53.720 回答
0

你有 2n 个元素的数组，一半是相同的，其余的是不同的，所以考虑以下情况，

ARRAY[2n] = {N,10,N,878,85778,N......};

或者

Array[2n] = {10,N,10,N,44,N......};

等等现在 for 循环中的简单案例，例如，

if(ARRAY[i] == ARRAY[i+1])
{
         //Your similar element :)
}
于 2013-06-01T12:17:55.380 回答