使用内存高效方法在数组中查找重复项
Find duplicate in array with a memory efficient approach
A
是一个整数数组。
所有值都在0
到A.Length-1
之间
表示0 <= A[i] <= A.Length-1
我应该找到重复的元素;如果有多个重复元素,则选择索引较低的元素作为重复项。
例如:
a = [3, 4, 2, 5, 2, 3]
然后
result = 2
这是一道面试题。我使用另一个数组来存储项目并检查它何时重复。然后它让我暂停了一些测试用例。
面试官建议只循环一次数组,不要创建任何额外的数据结构。
不需要另一种数据结构。您可以将输入本身用作哈希集。
每次看到一个值时,将 A.Length 添加到与该索引对应的项目。由于值可能已经递增,您应该将值视为 A[i] mod A.length
。
如果您找到一个已经 >= A.length.. 的项目,那么您就有了重复。 (请记住,问题表明所有项目都在 [0, A.Length-1]
区间内)
跟踪已找到的最低索引。
这导致 O(N) 复杂度(单次通过)并且没有使用额外的数据结构,即大小 O(1)
这种方法背后的关键概念是哈希集以这种方式工作。从概念上讲,这与鸽巢原理间接相关。
https://en.wikipedia.org/wiki/Pigeonhole_principle
注意:在面试过程中,询问具体实施问题、讨论限制、假设等很重要:
- 列表中项目的数据类型是什么?
- 如果值在 [0..A.length-1] 范围内,是否所有项目都没有符号,或者我可以根据需要使用负数吗?
- 等等
在面试过程中,我不会声称这是一个完美的答案,相反,我会与面试官讨论假设并相应地进行调整。例如,另一个答案建议使用负数,但项目的数据类型可能是无符号类型等
面试应该引发技术讨论,以探索您的知识和创造力。
注意:如果存在值为零的元素,则求解失败。 Olivier 的解决方案可以处理这种情况。
使索引为 A[i] 的元素为负数。它只经过一次循环。
for(int i=0; i<A.Length; i++)
{
if (A[Math.Abs(A[i])] < 0){ return Math.Abs(A[i]);}
A[Math.Abs(A[i])] = -A[Math.Abs(A[i])];
}
对于想要实现问题的人,我建议使用两种变体(在 c# 中,如在标签中),一种使用已接受的答案,另一种使用另一个答案的方法,使用相反的元素。然而,最后一个解决方案在零值方面存在问题,需要一些技巧。
第一个解决方案
using System;
public class Program
{
public static void Main()
{
int[] a = {3, 4, 0, 5, 2, 3};
int N = 6;
int min_index = 0;
bool found = false;
int index = -1;
int i = 0;
while(i < N && !found)
{
if(a[i] >= N)
index = a[i] % N;
else
index = a[i];
if(a[index] >= N) //its a duplicated elements
{
min_index = i;
found = true;
}else
{
a[index] += N;
}
i++;
}
Console.WriteLine("Result = " + a[min_index] % N);
}
}
第二种解决方案
using System;
public class Program
{
public static void Main()
{
int[] a = {3, 4, 2, 5, 2, 3};
int N = 6;
int min_index = N-1;
bool found = false;
int index = -1;
int i = 0;
while(i < N && !found)
{
if(a[i] == -N+1) //it was 0
index = 0;
else
index = Math.Abs(a[i]);
if(a[index] < 0 || a[index] == -N+1) //its a duplicated elements
{
min_index = i;
found = true;
}else
{
if(a[index] > 0)
{
a[index] = -a[index];
}else
{
a[index] += -N+1;
}
}
i++;
}
if(a[min_index] == -N+1)
a[min_index] = 0;
Console.WriteLine("Result = " + Math.Abs(a[min_index]));
}
}
我想改进@AryanFirouzian 的解决方案,并通过使用 yield return
return 所有重复项。此外,使用临时变量可以简化代码。
public static IEnumerable<int> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int absAi = Math.Abs(A[i]);
if (A[absAi] < 0) {
yield return absAi;
} else {
A[absAi] *= -1;
}
}
}
但是,此解决方案不会 return 具有较低索引的元素,如果有超过 2 个相同的副本,那么它将多次 return 相同的值。另一个问题是 0 不能为负数。
更好的解决方案消除了重复的结果,但仍然 return 是第二个索引并且存在 0 值的问题。它还returns索引本身来演示错误的索引问题
public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int x = A[i] % A.Length;
if (A[x] / A.Length == 1) {
yield return (i, x);
}
A[x] += A.Length;
}
}
测试
var A = new int[] { 3, 4, 2, 5, 2, 3, 3 };
foreach (var item in FindDuplicates(A)) {
Console.WriteLine($"[{item.index}] = {item.value}");
}
它returns
[4] = 2
[5] = 3
我的最终解决方案消除了所有这些问题(至少我希望如此):它通过将 (i + 1) * A.Length
添加到第一次出现的值来对第一个索引本身进行编码。 (i + 1)
因为 i
可以是 0
。然后可以使用反向操作解码索引 (A[x] / A.Length) - 1
.
然后,因为我们只想 return 第一个重复值的结果,我们将该值设置为负值以将其排除在进一步处理之外。随后,可以使用 Math.Abs(A[i]) % A.Length
.
检索原始值
public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int x = Math.Abs(A[i]) % A.Length;
if (A[x] >= 0) {
if (A[x] < A.Length) { // First occurrence.
A[x] += (i + 1) * A.Length; // Encode the first index.
} else { // Second occurrence.
int firstIndex = (A[x] / A.Length) - 1; // Decode the first index.
yield return (firstIndex, x);
// Mark the value as handeled by making it negative;
A[x] *= -1; // A[x] is always >= A.Length, so no zero problem.
}
}
}
}
Returns 预期结果
[2] = 2
[0] = 3
我们的元素是没有标识的整数。 IE。我们可以 return 任何索引处的重复项之一,因为无法区分两个相等的整数。如果元素有一个身份(它们可以是具有相同值但引用不同的引用类型,或者具有不参与相等性测试的其他字段),我们将不得不 return 第一次出现
yield return (firstIndex, Math.Abs(A[firstIndex]) % A.Length);
满足所有要求。
A
是一个整数数组。
所有值都在0
到A.Length-1
之间
表示0 <= A[i] <= A.Length-1
我应该找到重复的元素;如果有多个重复元素,则选择索引较低的元素作为重复项。
例如:
a = [3, 4, 2, 5, 2, 3]
然后
result = 2
这是一道面试题。我使用另一个数组来存储项目并检查它何时重复。然后它让我暂停了一些测试用例。 面试官建议只循环一次数组,不要创建任何额外的数据结构。
不需要另一种数据结构。您可以将输入本身用作哈希集。
每次看到一个值时,将 A.Length 添加到与该索引对应的项目。由于值可能已经递增,您应该将值视为 A[i] mod A.length
。
如果您找到一个已经 >= A.length.. 的项目,那么您就有了重复。 (请记住,问题表明所有项目都在 [0, A.Length-1]
区间内)
跟踪已找到的最低索引。
这导致 O(N) 复杂度(单次通过)并且没有使用额外的数据结构,即大小 O(1)
这种方法背后的关键概念是哈希集以这种方式工作。从概念上讲,这与鸽巢原理间接相关。 https://en.wikipedia.org/wiki/Pigeonhole_principle
注意:在面试过程中,询问具体实施问题、讨论限制、假设等很重要: - 列表中项目的数据类型是什么? - 如果值在 [0..A.length-1] 范围内,是否所有项目都没有符号,或者我可以根据需要使用负数吗? - 等等
在面试过程中,我不会声称这是一个完美的答案,相反,我会与面试官讨论假设并相应地进行调整。例如,另一个答案建议使用负数,但项目的数据类型可能是无符号类型等
面试应该引发技术讨论,以探索您的知识和创造力。
注意:如果存在值为零的元素,则求解失败。 Olivier 的解决方案可以处理这种情况。
使索引为 A[i] 的元素为负数。它只经过一次循环。
for(int i=0; i<A.Length; i++)
{
if (A[Math.Abs(A[i])] < 0){ return Math.Abs(A[i]);}
A[Math.Abs(A[i])] = -A[Math.Abs(A[i])];
}
对于想要实现问题的人,我建议使用两种变体(在 c# 中,如在标签中),一种使用已接受的答案,另一种使用另一个答案的方法,使用相反的元素。然而,最后一个解决方案在零值方面存在问题,需要一些技巧。
第一个解决方案
using System;
public class Program
{
public static void Main()
{
int[] a = {3, 4, 0, 5, 2, 3};
int N = 6;
int min_index = 0;
bool found = false;
int index = -1;
int i = 0;
while(i < N && !found)
{
if(a[i] >= N)
index = a[i] % N;
else
index = a[i];
if(a[index] >= N) //its a duplicated elements
{
min_index = i;
found = true;
}else
{
a[index] += N;
}
i++;
}
Console.WriteLine("Result = " + a[min_index] % N);
}
}
第二种解决方案
using System;
public class Program
{
public static void Main()
{
int[] a = {3, 4, 2, 5, 2, 3};
int N = 6;
int min_index = N-1;
bool found = false;
int index = -1;
int i = 0;
while(i < N && !found)
{
if(a[i] == -N+1) //it was 0
index = 0;
else
index = Math.Abs(a[i]);
if(a[index] < 0 || a[index] == -N+1) //its a duplicated elements
{
min_index = i;
found = true;
}else
{
if(a[index] > 0)
{
a[index] = -a[index];
}else
{
a[index] += -N+1;
}
}
i++;
}
if(a[min_index] == -N+1)
a[min_index] = 0;
Console.WriteLine("Result = " + Math.Abs(a[min_index]));
}
}
我想改进@AryanFirouzian 的解决方案,并通过使用 yield return
return 所有重复项。此外,使用临时变量可以简化代码。
public static IEnumerable<int> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int absAi = Math.Abs(A[i]);
if (A[absAi] < 0) {
yield return absAi;
} else {
A[absAi] *= -1;
}
}
}
但是,此解决方案不会 return 具有较低索引的元素,如果有超过 2 个相同的副本,那么它将多次 return 相同的值。另一个问题是 0 不能为负数。
更好的解决方案消除了重复的结果,但仍然 return 是第二个索引并且存在 0 值的问题。它还returns索引本身来演示错误的索引问题
public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int x = A[i] % A.Length;
if (A[x] / A.Length == 1) {
yield return (i, x);
}
A[x] += A.Length;
}
}
测试
var A = new int[] { 3, 4, 2, 5, 2, 3, 3 };
foreach (var item in FindDuplicates(A)) {
Console.WriteLine($"[{item.index}] = {item.value}");
}
它returns
[4] = 2
[5] = 3
我的最终解决方案消除了所有这些问题(至少我希望如此):它通过将 (i + 1) * A.Length
添加到第一次出现的值来对第一个索引本身进行编码。 (i + 1)
因为 i
可以是 0
。然后可以使用反向操作解码索引 (A[x] / A.Length) - 1
.
然后,因为我们只想 return 第一个重复值的结果,我们将该值设置为负值以将其排除在进一步处理之外。随后,可以使用 Math.Abs(A[i]) % A.Length
.
public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int x = Math.Abs(A[i]) % A.Length;
if (A[x] >= 0) {
if (A[x] < A.Length) { // First occurrence.
A[x] += (i + 1) * A.Length; // Encode the first index.
} else { // Second occurrence.
int firstIndex = (A[x] / A.Length) - 1; // Decode the first index.
yield return (firstIndex, x);
// Mark the value as handeled by making it negative;
A[x] *= -1; // A[x] is always >= A.Length, so no zero problem.
}
}
}
}
Returns 预期结果
[2] = 2
[0] = 3
我们的元素是没有标识的整数。 IE。我们可以 return 任何索引处的重复项之一,因为无法区分两个相等的整数。如果元素有一个身份(它们可以是具有相同值但引用不同的引用类型,或者具有不参与相等性测试的其他字段),我们将不得不 return 第一次出现
yield return (firstIndex, Math.Abs(A[firstIndex]) % A.Length);
满足所有要求。