logo标签列表

在数组中查找重复项

carraysduplicates
4
我知道如何在数组中查找重复元素，但最近在一次面试中，我被要求在单次遍历数组中查找重复元素，这意味着不能使用嵌套循环和递归。我尝试了，但失败了。 面试官甚至没有给我提示。 所以我来这里问，是否可以在不使用嵌套循环/递归的情况下找到数组中的重复元素？ 如果是，请问有人能提供一个示例代码吗？同时，库函数不允许使用。
另外，如果我们不使用循环或递归，会对复杂度产生什么影响？
2
@blazs 你不能在单次遍历中对数组进行排序。 - tofro
哦，对了。看起来你应该向面试官询问细节。你能假设元素是整数吗？如果可以，那么你可以使用计数排序进行排序。如果不行，那么你可以使用哈希表，并且期望时间复杂度为O(n)。等等。 - blazs
我们不知道面试官到底问了你什么，但根据你的问题所述，这是不可能的。 - n. m.
这是可能的，下面已经给出了解决方案（尽管效率极低）。然而，我认为原始问题中并没有提出所有约束条件。这样的问题通常会有一个扭曲的地方，比如“在1..（n + 1）数组中具有一个重复项的1..n整数”。 - tofro
@tofro 所有这些解决方案都假设问题中没有说明的内容，或违反了已经说明的要求。如果您可以假设任何您想要的东西，那么您就可以解决任何问题。为什么不假设数组包含布尔值并结束呢？不，等等，那太愚蠢了，让我们使用字典！好的。由于不允许使用库函数、嵌套循环或递归，那么如何实现一个字典呢？ - n. m.
显示剩余3条评论
5个回答
4
您可以使用哈希表/字典来存储每个项目值的计数。
@n.m. 为什么不允许编写自己的哈希表？ - autistic
@Seb 尝试不使用循环或递归来完成。 - n. m.
不使用嵌套循环？当然可以。可以使用 continue 将多个循环合并为一个。 - autistic
@n.m. 你刚刚改变了目标...一开始你谈论的是“循环和递归”的要求，现在你又转移到了其他要求。你意识到你对第一个要求是错误的了吗？没关系，我很乐意继续...你没有足够的信息来推断“在单次遍历中查找数组中的重复元素”与“不能执行其他数组的遍历”之间的关系。 - autistic
@n.m. 这是一个循环，每个元素只被访问一次，是的。这是否意味着它不能在每个元素访问时循环多次？ - autistic
显示剩余3条评论
0

由于您想要在线性时间内查找重复项，例如一次遍历，因此必须使用附加的数据结构来计算每个元素出现的次数。

在这里，我假设数组是整数类型。但是，这对于任何类型都适用。我使用一个HashMap，将元素（在本例中为整数）用作键，将出现次数用作值。

public static ArrayList<Integer> findDuplicates(int[] arr) {

   HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
   for (int i = 0; i < arr.length; i++) {
       if (!map.containsKey(arr[i]))
           map.put(arr[i], 1);
       else
           map.put(arr[i], map.get(arr[i]) + 1);
   }

   ArrayList<Integer> dups = new ArrayList<Integer>();

   for (Integer i : map.keySet())
       if (map.get(i) > 1)
            dups.add(i);

  return dups;
}

所以

int arr[] = {1,2,3,4,2,1,2,3,4,5,6,7,8};
findDuplicates(arr);

将返回[1, 2, 3, 4]。

0

由于您没有提及数组，我认为无法在单次遍历中完成。我不确定计数排序是否是您要寻找的答案。因此，解决您问题的唯一方法是使用字典。这是我在C语言中找到的最简单的字典实现。

C语言中实现字典的快速方法

希望这可以帮助您。

-1

我假设整数的大小为2个字节。

#define ARRAY_SIZE 10

int array[ARRAY_SIZE] = {2,3,1,5,1,6,7,7,8,1};

int duplicate[65535] = {0};

for(char i = 0;i< ARRAY_SIZE;i++)
{
  duplicate[array[i]]++;
  if(duplicate[array[i]] > 1)
  {
     printf(" %d is duplicate in array",array[i]);
  }  
}

现在，duplicate 数组的每个索引显示了一个值在 array 中重复出现的次数。
（1）这个假设是不合理的。（2）这不是一个O(n)的解决方案。请看我对另一个错误答案的解释，就会明白为什么这样是错的。 - Tom Karzes
@TomKarzes 我正在使用78K0R编译器工作，其中整数的大小为2个字节。 - Vagish
@TomKarzes 请再仔细阅读一遍问题，我已经给出了可以解决该问题的O(n)答案。您认为它不实用（对于您的系统），所以您将我的答案投了反对票。我仍然不确定这个答案是否错了？ - Vagish
不，你提供的解决方案非常低效，只有在（1）数组包含整数且（2）整数很小以至于你愿意创建一个足够大的数组来支持每个可能的整数值作为索引时才能工作。这两个假设都是不合理的。我无法再更清楚地解释了。 - Tom Karzes
让我们在聊天中继续这个讨论。 - Vagish
显示剩余3条评论
-1

简单而有创意的解决方案： 提出要求，数组应该被排序 - 然后它就会变得微不足道。（但这就是面试问题的工作方式）

1
我认为我们可以安全地假设回答是“很不错，但并不是这样”。 - Tom Karzes
我不这么认为 - 我面试的地方不是这样子的。我更喜欢听到有创意的回答，而不是书本上的答案。其他答案中提出的哈希表是一个完美的解决方案，但并不能导致一个完美的程序。如果你遇到了查找重复项的实际情况，那么当要求一个排序数组时，你可能可以大大提高代码质量 - 这在现实中可能是小菜一碟。 - tofro
1
我认为如果数组已排序，那么这个问题太琐碎了，不值得一提。既然如此，为什么还要问这个问题呢？如果遇到这个问题，我可能会确认一下：“我假设数组是未排序的？”只是为了让面试官知道我已经考虑过这个问题，但如果回答是“不，它已经排序好了，下一个问题”，我会感到非常惊讶。这有什么意义呢？ - Tom Karzes
重点是：我希望候选人提出最简单的解决方案。即使需要讨论和在其他地方重新工作。因为这就是我期望在我的团队中工作的工程师所做的。哈希是给定约束条件下的一个不错的解决方案，但如果你在真正的团队中这样做，你可能会被解雇... - tofro
说起来，如果你不要求一个已排序的数组，我可能不会雇用你。就是这样。 - tofro
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接