在小于线性的时间内，在排序的数组中找到副本 [英] In less-than-linear time, find the duplicate in a sorted array

问题描述

今天，面试官问我这个问题。我立即的回答是，我们可以简单地进行线性搜索，将当前元素与数组中的上一个元素进行比较。然后他问我如何在不到线性的时间内解决问题。

假设

• 数组是排序


• 只有一个重复


• 数组仅填入数字 [0，n] ，其中 n 是数组的长度。

示例数组：[0,1 ，2,3,4,5,6,7,8,8,9]

我试图提出一个分治算法来解决这个问题，但我不确定这是正确的答案。有没有人有任何想法？

解决方案

可以用O（log N）修改二进制搜索：

从数组的中间开始：如果array [idx]< idx的副本是在左边，否则在右边。冲洗并重复。

Today, an interviewer asked me this question. My immediate response was that we could simply do a linear search, comparing the current element with the previous element in the array. He then asked me how the problem could be solved in less-than-linear time.

Assumptions

• The array is sorted
• There is only one duplicate
• The array is only populated with numbers [0, n], where n is the length of the array.

Example array: [0,1,2,3,4,5,6,7,8,8,9]

I attempted to come up with a divide-and-conquer algorithm to solve this, but I'm not confident that it was the right answer. Does anyone have any ideas?

解决方案

Can be done in O(log N) with a modified binary search:

Start in the middle of the array: If array[idx] < idx the duplicate is to the left, otherwise to the right. Rinse and repeat.

这篇关于在小于线性的时间内，在排序的数组中找到副本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！