我在面试中遇到了一个问题,我无法回答。
你需要在数组中找到第一个唯一的元素(整数)。
例如:
3,2,1,4,4,5,6,6,7,3,2,3
唯一的元素是
1, 5, 7
,其中第一个唯一的元素是1
。所需解决方案:
我尝试使用哈希表、位向量等方法,但它们都没有O(1)的空间复杂度。O(n)时间复杂度。
O(1)空间复杂度。
有人能告诉我空间复杂度为O(1)的解决方案吗?
我在面试中遇到了一个问题,我无法回答。
你需要在数组中找到第一个唯一的元素(整数)。
例如:
3,2,1,4,4,5,6,6,7,3,2,3
1, 5, 7
,其中第一个唯一的元素是1
。我尝试使用哈希表、位向量等方法,但它们都没有O(1)的空间复杂度。O(n)时间复杂度。
O(1)空间复杂度。
O(n)时间复杂度,O(1)空间复杂度
的重复检测是不可能的吗? - us2012OP的问题原始版本没有提到数字的限制(尽管后来添加的数字可以是负数/正数/零)。在这里,我假设还有一个条件:
数组中的数字都比数组长度小且非负。
那么,给出一个O(n)时间,O(1)空间的解决方案是可能的,而且似乎是一道面试题,而且OP在问题中给出的测试用例符合上述假设。
解决方案:
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i) {
if (nums[i] == -1) continue;
if (nums[nums[i]] == nums[i]) {
nums[nums[i]] = -1;
} else {
swap(nums, nums[i], i);
i--;
}
}
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] == i) {
return i;
}
}
这里的算法将原始数组视为桶排序中的桶。将数字放入其桶中,如果超过两次,则将其标记为-1。使用另一个循环来查找第一个满足 nums[i] == i 的数字。
注意:这种方法并不适用于所有情况。请参见下面的推理。
原始想法
也许有一种O(n)时间和O(1)额外空间的解决方案。
可以在O(n)时间内构建堆。请参见构建堆。
因此,您可以反向构建堆,从数组中的最后一个元素开始,并使该位置成为根。在构建堆时,跟踪最近的非重复项。
这假设在将项目插入堆时,您会遇到已经存在于堆中的任何相同项目。我不知道我能否证明这一点……
假设上述内容是正确的,那么当您完成构建堆时,您就知道哪个项目是第一个非重复项目。
为什么它行不通
构建就地堆的算法从数组中点开始,并假定该点之后的所有节点都是叶节点。然后它向后工作(朝向项0),将项筛选到堆中。该算法不按特定顺序检查任何最后n/2个项,而且随着项被筛入堆中,顺序会发生变化。2
的元素。 - Jim Mischel我认为这是不可能的。这不是一个证明,而是一个猜想的证据。我的推理如下...
首先,你说元素的值没有上限(它们可以是负数、0或正数)。其次,只有O(1)
的空间,所以我们不能存储超过固定数量的值。因此,这意味着我们必须仅使用比较来解决这个问题。此外,我们不能对数组中的值进行排序或交换,因为我们会失去唯一值的原始顺序(我们也无法存储原始顺序)。
考虑一个所有整数都是唯一的数组:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1
,我们需要将每个元素与所有其他元素进行比较,以确保它是唯一的,并且要按相反的顺序进行比较,这样我们可以最后检查第一个唯一元素。这将需要O(n^2)
次比较和O(1)
的空间。O(n)
次比较来证明第一个元素是唯一的。 - John Dvorak