找到一个排序的数组中不可复制的元素 [英] Find the unduplicated element in a sorted array

问题描述

来源：微软面试问题的

Source : Microsoft Interview Question

给定一个排序后的数组，其中每个元素是present两次，除了一个是present单的时候，我们需要找到一个元素。

Given a sorted array, in which every element is present twice except one which is present single time, we need to find that element.

现在标准为O（n）解决方案是做一个XOR名单，这将返回不重复的元素（因为所有的重复元素相互抵消。）

Now a standard O(n) solution is to do a XOR of list, which will return the unduplicated element (since all duplicated elements cancel out.)

是否有可能更迅速地解决这个问题，如果我们知道数组排序？

Is it possible to solve this more quickly if we know the array is sorted?

推荐答案

是的，你可以用有序性通过执行来降低复杂性 O（log n）的二进制搜索。

Yes, you can use the sortedness to reduce the complexity to O(log n) by doing a binary search.

由于数组排序，缺少的元素之前，每个值占点 2 * K 和 2 * K + 1 阵列中（假设基于0的索引）。

Since the array is sorted, before the missing element, each value occupies the spots 2*k and 2*k+1 in the array (assuming 0-based indexing).

所以，你到数组中间，说指数 ^ h ，并检查无论是指数 H + 1 如果 ^ h 是偶数，或 H-1 如果 ^ h 为奇数。如果缺少的元素出现得较晚，在这些位置的值相等，如果它之前，值不同。重复，直到缺少的元素所在。

So you go to the middle of the array, say index h, and check either index h+1 if h is even, or h-1 if h is odd. If the missing element comes later, the values at these positions are equal, if it comes before, the values are different. Repeat until the missing element is located.

这篇关于找到一个排序的数组中不可复制的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！