c++ - 谈数组时两次比较的意义

Question

这是来自网站的确切问题。

给定一个有 10 个元素的排序数组，其中包含 6 个不同的数字，其中只有 1 个数字重复了五次。您的任务是仅使用两次比较来找到重复的数字。

我不确定这里的“两次比较”是什么意思。你能解释一下吗？谢谢。

以下是我回答这个问题的代码。

using namespace std;

int FindDuplicate(vector<int>& nums)
{

int count = 1, marked = 0;

for (int i = 0; i < nums.size(); i++)
{       

    if (nums[i + 1] == nums[marked])
    {
        count++;

        if (count == 5)
            return nums[marked];
    }

    else
    {
        marked = i + 1;
        count = 1;
    }
}

return 0;
}

Answer 1

这里2个比较意味着你只执行2个比较的原始操作。

if(a > b)可以认为是1个比较。但是

if(a > b && c < d)被认为是2次比较。

if(a > b)执行2次也是2次比较。

现在由于数组已排序并且只有6 个不同的元素:

我们可以很容易地列出数组元素的各种可能性并得出结论:

index 5 处的元素等于:

Element at index 6，本例中的答案是element at index 6

否则

索引 4 处的元素 就是答案。

所以解决方案是:

if(array[5] == array[6])
 return array[5];
else return array[4];