c - 检查matrix[1000][1000]中重复元素的解决方法

Question

需要编写检查矩阵[1000][1000]中重复元素的函数。如果发现任何重复元素，则返回 True，否则返回 False。

我认为需要分两步来解决:1.将矩阵中的每个元素从小到大排序(在排序过程中我们可以检查元素是否相等)例如使用归并排序。2. 从矩阵中的第一个元素到最后一个元素逐个比较上一个元素和下一个元素。

这个解决方案的效率是否足够好？

Answer 1

这是 element distinctness problem ，并且你的数组是二维的似乎并不重要，你可以将其视为“常规”数组，并使用元素差异的“常规”解决方案解决它，即:

1. 对数组进行排序，然后迭代元素并检查是否存在满足 arr[i] == arr[i+1] 的索引 i。
   这个解决方案是 O(nlogn) 时间，假设高效排序，几乎不需要额外的空间。
2. 将元素存储在哈希集中，并在插入每个元素时检查该元素是否已存在于集合中。
   这个解决方案是 O(n) 时间平均，O(n^2) 时间最坏情况，并且需要 O(n) 额外空间。