64

我在工作面试中被问到这个问题,我一直想知道正确的答案。

您有一个从 0 到 n-1 的数字数组,其中一个数字被删除,并替换为数组中已有的数字,该数字与该数字重复。我们如何在O(n)时间内检测到这个重复?

例如,一个数组4,1,2,3将变为4,1,2,2.

时间O(n 2 )的简单解决方案是使用嵌套循环来查找每个元素的重复项。

4

24 回答 24

155

这可以在O(n)时间和O(1)空间上完成。

(该算法之所以有效,是因为这些数字是已知范围内的连续整数):

在一次通过向量的过程中,计算所有数字的总和,以及所有数字的平方和。

减去所有数字的总和N(N-1)/2。打电话给这个A

从 中减去平方和N(N-1)(2N-1)/6。将此除以A。调用结果B

被删除(B + A)/2的数字是 和它被替换的数字是(B - A)/2

例子:

向量是[0, 1, 1, 2, 3, 5]

  • N = 6

  • 向量之和为 0 + 1 + 1 + 2 + 3 + 5 = 12。N(N-1)/2 为 15。A = 3。

  • 平方和为 0 + 1 + 1 + 4 + 9 + 25 = 40。N(N-1)(2N-1)/6 为 55。B = (55 - 40)/A = 5。

  • 删除的数字是 (5 + 3) / 2 = 4。

  • 它被替换的数字是 (5 - 3) / 2 = 1。

为什么有效:

  • 原始向量之和[0, ..., N-1]N(N-1)/2。假设该值a已被删除并替换为b. 现在修改向量的总和将是N(N-1)/2 + b - a。如果我们从中减去修改后的向量之和,则N(N-1)/2得到a - b。所以A = a - b

  • 类似地,原始向量的平方和为N(N-1)(2N-1)/6。修正向量的平方和为。从原始和中减去修改向量的平方和得到,与 相同。因此,如果我们将它除以(ie, ),我们得到。N(N-1)(2N-1)/6 + b2 - a2a2 - b2(a+b)(a-b)a - bAB = a + b

  • 现在B + A = a + b + a - b = 2aB - A = a + b - (a - b) = 2b

于 2013-02-18T22:50:06.473 回答
34

我们有原始数组int A[N];创建第二个数组bool B[N],类型为bool=false。迭代第一个数组并设置B[A[i]]=trueif 为 false,否则 bing!

于 2013-02-18T20:26:21.703 回答
32

您可以在 O(N) 时间内完成,无需任何额外空间。这是算法的工作原理:

以下列方式遍历数组:

  1. 对于遇到的每个元素,将其对应的索引值设置为负数。例如:如果你发现 a[0] = 2。得到 a[2] 并否定该值。

    通过这样做,您可以将其标记为遇到。既然你知道你不能有负数,你也知道你是否定它的人。

  2. 检查与该值对应的索引是否已标记为负,如果是,则您得到重复的元素。例如:如果 a[0]=2 ,转到 a[2] 并检查它是否为负数。

假设您有以下数组:

int a[]  = {2,1,2,3,4};

在第一个元素之后,您的数组将是:

int a[] = {2,1,-2,3,4};

在第二个元素之后,您的数组将是:

int a[] = {2,-1,-2,3,4};

当您到达第三个元素时,您会转到 a[2] 并看到它已经为负数。你得到副本。

于 2013-05-30T13:20:06.843 回答
11

扫描阵列 3 次:

  1. 将所有数组元素 XOR 在一起-> A。将 0 到 N-1 -> 的所有数字异或B。现在A XOR B = X XOR D,其中 X 是删除的元素,D 是重复的元素。
  2. 选择 中的任何非零位A XOR B将设置此位的所有数组元素 XOR 在一起-> A1。将所有从 0 到 N-1 的数字 XOR 在一起,其中设置了该位 -> B1。现在要么A1 XOR B1 = X要么A1 XOR B1 = D
  3. 再次扫描阵列并尝试找到 A1 XOR B1. 如果找到,这是重复元素。如果不是,则重复元素是A XOR B XOR A1 XOR B1.
于 2013-02-18T20:42:31.703 回答
7

使用 aHashSet保存所有已经看到的数字。它在(摊销)O(1)时间内运行,因此总数为O(N)

于 2013-02-18T20:12:33.683 回答
7

我建议使用 BitSet。我们知道 N 对于数组索引来说足够小,所以 BitSet 的大小是合理的。

对于数组的每个元素,检查与其值对应的位。如果已经设置,那就是副本。如果没有,请设置该位。

于 2013-02-18T20:23:32.513 回答
4

@rici 关于时间和空间的使用是正确的:“这可以在 O(n) 时间和 O(1) 空间内完成。”

但是,这个问题可以扩展到更广泛的要求:重复的数字不一定只有一个,而且数字可能不是连续的。

OJ在这里这样说:(注3显然可以缩小)

给定一个包含 n + 1 个整数的数组 nums,其中每个整数介于 1 和 n(含)之间,证明至少存在一个重复数。假设只有一个重复的号码,找到重复的号码。

笔记:

  • 您不得修改数组(假设数组是只读的)。
  • 您必须只使用常量,O(1) 额外空间。
  • 您的运行时复杂度应小于 O(n2)。
  • 数组中只有一个重复的数字,但可以重复多次。

Keith Schwarz在这里使用Floyd 的循环查找算法很好地解释和回答了这个问题:

我们需要用来解决这个问题的主要技巧是注意,因为我们有一个包含从 0 到 n - 2 的 n 个元素的数组,我们可以将数组视为从集合 {0, 1, ..., n - 1} 到自身上。该函数由 f(i) = A[i] 定义。鉴于此设置,重复值对应于一对索引 i != j 使得 f(i) = f(j)。因此,我们的挑战是找到这对 (i, j)。一旦我们有了它,我们只需选择 f(i) = A[i] 即可轻松找到重复值。

但是我们如何找到这个重复值呢?事实证明,这是计算机科学中一个经过充分研究的问题,称为循环检测。问题的一般形式如下。我们得到一个函数 f。将序列 x_i 定义为

    x_0     = k       (for some k)
    x_1     = f(x_0)
    x_2     = f(f(x_0))
    ...
    x_{n+1} = f(x_n)

假设 f 从域映射到自身,则此函数将具有三种形式之一。首先,如果域是无限的,那么序列可以是无限长且不重复的。例如,整数上的函数 f(n) = n + 1 具有此属性 - 没有数字是重复的。其次,该序列可能是一个闭环,这意味着存在一些 i 使得 x_0 = x_i。在这种情况下,序列会无限期地循环通过一些固定的值集。最后,序列可以是“rho 形”。在这种情况下,序列看起来像这样:

 x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                    ^                       |
                    |                       |
                    +-----------------------+

也就是说,序列从进入循环的元素链开始,然后无限循环。我们将在序列中到达的循环的第一个元素表示为循环的“入口”。

也可以在这里找到一个 python 实现:

def findDuplicate(self, nums):
    # The "tortoise and hare" step.  We start at the end of the array and try
    # to find an intersection point in the cycle.
    slow = 0
    fast = 0

    # Keep advancing 'slow' by one step and 'fast' by two steps until they
    # meet inside the loop.
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    # Start up another pointer from the end of the array and march it forward
    # until it hits the pointer inside the array.
    finder = 0
    while True:
        slow   = nums[slow]
        finder = nums[finder]

        # If the two hit, the intersection index is the duplicate element.
        if slow == finder:
            return slow
于 2016-06-22T02:52:34.073 回答
3

使用哈希表。在哈希表中包含一个元素是 O(1)。

于 2013-02-18T20:12:05.297 回答
2

一种可行的解决方案:

假设数字是整数

创建一个 [0 .. N] 的数组

int[] counter = new int[N];

然后迭代读取并增加计数器:

 if (counter[val] >0) {
   // duplicate
 } else {
   counter[val]++;
 }
于 2013-02-18T20:26:58.140 回答
2

这可以在O(n)时间和O(1)空间内完成。 不修改输入数组

  1. 这个想法类似于在链表中找到循环的起始节点。
  2. 保持两个指针:快和慢
slow = a[0]
fast = a[a[0]]
  1. 循环直到慢!=快
  2. 一旦我们找到循环(慢==快)
  3. 将慢速重置为零
slow = 0
  1. 找到起始节点
while(slow != fast){
    slow = a[slow];
    fast = a[fast];
}
  1. 慢是你的重复号码。

这是一个Java实现:

class Solution {
    public int findDuplicate(int[] nums) {
        if(nums.length <= 1) return -1;
        int slow = nums[0], fast = nums[nums[0]]; //slow = head.next, fast = head.next.next
        while(slow != fast){            //check for loop
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        if(slow != fast) return -1;
        slow = 0; //reset one pointer
        while(slow != fast){ //find starting point of loop
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
于 2019-06-02T09:02:32.613 回答
1

这是O(n)时间和O(1)空间上的另一种解决方案。它类似于rici 的. 我发现它更容易理解,但在实践中,它会溢出得更快。

X成为缺失的数字并R成为重复的数字。

  1. 我们可以假设数字来自[1..n],即不出现零。实际上,在遍历数组时,我们可以测试是否找到零,如果没有则立即返回。

  2. 现在考虑:

    sum(A) = n (n + 1) / 2 - X + R
    
    product(A) = n! R / X
    

其中product(A)A跳过零的所有元素的乘积。我们有两个具有两个未知数的方程,从中可以代数推导出X和。R

编辑:根据大众的需求,这里有一个成功的例子:

让我们设置:

S = sum(A) - n (n + 1) / 2
P = n! / product(A)

那么我们的方程就变成了:

R - X = S
X = R P

可以解决:

R = S / (1 - P)
X = P R = P S / (1 - P)

例子:

A = [0 1 2 2 4]

n = A.length - 1 = 4
S = (1 + 2 + 2 + 4) - 4 * 5 / 2 = -1
P = 4! / (1 * 2 * 2 * 4) = 3 / 2

R = -1 / (1 - 3/2) = -1 / -1/2 = 2
X = 3/2 * 2 = 3
于 2017-01-11T20:55:01.620 回答
0

您可以进行如下操作:

  1. 使用线性时间排序算法(例如计数排序)对数组进行排序 - O(N)
  2. 扫描已排序的数组并在两个连续元素相等时立即停止 - O(N)
于 2013-02-18T21:33:55.753 回答
0
public class FindDuplicate {
    public static void main(String[] args) {
        // assume the array is sorted, otherwise first we have to sort it.
        // time efficiency is o(n)
        int elementData[] = new int[] { 1, 2, 3, 3, 4, 5, 6, 8, 8 };
        int count = 1;
        int element1;
        int element2;

        for (int i = 0; i < elementData.length - 1; i++) {
            element1 = elementData[i];
            element2 = elementData[count];
            count++;
            if (element1 == element2) {
                System.out.println(element2);
            }
        }
    }
}
于 2014-04-21T00:10:32.423 回答
0
  public void duplicateNumberInArray {
    int a[] = new int[10];
    Scanner inp = new Scanner(System.in);
    for(int i=1;i<=5;i++){  
        System.out.println("enter no. ");
        a[i] = inp.nextInt();
    }
    Set<Integer> st = new HashSet<Integer>();
    Set<Integer> s = new HashSet<Integer>();
    for(int i=1;i<=5;i++){          
        if(!st.add(a[i])){
            s.add(a[i]);
        }
    }

    Iterator<Integer> itr = s.iterator();
                System.out.println("Duplicate numbers are");
    while(itr.hasNext()){
        System.out.println(itr.next());
    }
}

首先使用 Scanner 类创建一个整数数组。然后遍历数字循环并检查是否可以将数字添加到集合中(仅当该特定数字不应该在集合中时才可以将数字添加到集合中,这意味着集合不允许重复的数字添加并返回布尔值vale FALSE 添加重复值)。如果没有。不能添加意味着它是重复的,所以将该重复的数字添加到另一个集合中,以便我们稍后打印。请注意我们正在将重复数字添加到集合中,因为重复数字可能会重复多次,因此只添加一次。最后我们使用迭代器打印集合。

于 2014-09-17T08:57:52.190 回答
0

//这类似于HashSet方法,但只使用一种数据结构:

    int[] a = { 1, 4, 6, 7, 4, 6, 5, 22, 33, 44, 11, 5 };

    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();

    for (int i : a) {
        map.put(i, map.containsKey(i) ? (map.get(i)) + 1 : 1);
    }

    Set<Entry<Integer, Integer>> es = map.entrySet();
    Iterator<Entry<Integer, Integer>> it = es.iterator();

    while (it.hasNext()) {
        Entry<Integer, Integer> e = it.next();
        if (e.getValue() > 1) {
            System.out.println("Dupe " + e.getKey());
        }
    }
于 2014-10-10T23:38:06.597 回答
0

我们可以有效地使用 hashMap:

Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int x : a)
{
    if (map.containsKey(x))  map.put(x,map.get(x)+1);
    else map.put(x,1);
}

Integer [] keys = map.keySet().toArray(new Integer[map.size()]);
for(int x : keys)
{
    if(map.get(x)!=1)
    {
        System.out.println(x+" repeats : "+map.get(x));
    }
}
于 2015-04-23T09:51:17.283 回答
0

这个程序是基于c#的,如果你想用另一种编程语言来做这个程序,你必须首先按升序更改数组并将第一个元素与第二个元素进行比较。如果相等,则找到重复的数字。程序是

int[] array=new int[]{1,2,3,4,5,6,7,8,9,4};
Array.Sort(array);
for(int a=0;a<array.Length-1;a++)
{
  if(array[a]==array[a+1]
  {
     Console.WriteLine("This {0} element is repeated",array[a]);
   }
}
Console.WriteLine("Not repeated number in array");
于 2015-09-07T13:17:17.193 回答
0
  1. 对数组进行排序 O(n ln n)
  2. 使用滑动窗口技巧遍历数组 O(n)

    空间是 O(1)

    Arrays.sort(input);
    for(int i = 0, j = 1; j < input.length ; j++, i++){
        if( input[i] == input[j]){
            System.out.println(input[i]);
            while(j < input.length && input[i] == input[j]) j++;
            i = j - 1;
        }
    }
    

测试用例 int[] { 1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7 }

输出 1、2、3、7

于 2015-09-14T02:58:26.353 回答
0

遍历数组并检查 的符号array[abs(array[i])],如果为正则为负,如果为负则打印,如下:

import static java.lang.Math.abs;

public class FindRepeatedNumber {

    private static void findRepeatedNumber(int arr[]) {
        int i;
        for (i = 0; i < arr.length; i++) {
            if (arr[abs(arr[i])] > 0)
                arr[abs(arr[i])] = -arr[abs(arr[i])];
            else {
                System.out.print(abs(arr[i]) + ",");
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
        findRepeatedNumber(arr);
    }
}

参考: http ://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

于 2016-01-16T11:09:43.087 回答
0

如前所述,

您有一个从 0 到 n-1 的数字数组,其中一个数字被删除,并替换为数组中已有的数字,该数字与该数字重复。

我假设数组中的元素除重复条目外已排序。如果是这种情况,我们可以轻松实现以下目标:

        public static void main(String[] args) {
    //int arr[] = { 0, 1, 2, 2, 3 };
    int arr[] = { 1, 2, 3, 4, 3, 6 };
    int len = arr.length;
    int iMax = arr[0];
    for (int i = 1; i < len; i++) {
        iMax = Math.max(iMax, arr[i]);
        if (arr[i] < iMax) {
            System.out.println(arr[i]);
            break;
        }else if(arr[i+1] <= iMax) {
            System.out.println(arr[i+1]);
            break;
        }
    }
}
  • O(n) 时间和 O(1) 空间;请分享您的想法。
于 2017-06-23T17:08:09.080 回答
0

这是在 O(n) 时间内使用 hashmap 的简单解决方案。

#include<iostream>
#include<map>
using namespace std;

int main()
{
    int a[]={1,3,2,7,5,1,8,3,6,10};
    map<int,int> mp;
    for(int i=0;i<10;i++){

        if(mp.find(a[i]) == mp.end())
            mp.insert({a[i],1});
        else
            mp[a[i]]++;
    }

    for(auto i=mp.begin();i!=mp.end();++i){
        if(i->second > 1)
            cout<<i->first<<" ";
    }

}
于 2019-07-25T08:32:52.367 回答
0
int[] a = {5, 6, 8, 9, 3, 4, 2, 9 };
int[] b = {5, 6, 8, 9, 3, 6, 1, 9 };

 for (int i = 0; i < a.Length; i++)
  {
     if (a[i] != b[i])
      {
       Console.Write("Original Array manipulated at position {0}  + "\t\n"  
                             + "and the element is {1} replaced by {2} ", i, 
                             a[i],b[i] + "\t\n" );
       break;               
      }      
  }
   Console.Read();

   ///use break if want to check only one manipulation in original array.
   ///If want to check more then one manipulation in original array, remove break
于 2020-02-11T09:54:11.903 回答
0

这个视频如果编程是一部动漫太有趣了,不能分享。这是同样的问题,视频有答案:

  1. 排序
  2. 创建哈希图/字典。
  3. 创建一个数组。(虽然这部分被跳过了。)
  4. 使用龟兔算法。

注意:这个问题更像是一个琐事问题,而不是现实世界。哈希图之外的任何解决方案都是过早的优化,除非在罕见的有限内存情况下,如嵌入式编程。

此外,您最后一次在现实世界中看到一个数组,其中数组中的所有变量都适合数组的大小是什么时候?例如,如果数组中的数据是字节(0-255),那么您是否有一个包含 256 个元素或更大元素且其中没有 null 或 inf 的数组,并且您需要找到一个重复的数字?这种情况非常罕见,你可能在整个职业生涯中都不会使用这个技巧。

因为这是一个琐事问题,而不是现实世界的问题,所以我会谨慎接受一家提出此类琐事问题的公司的报价,因为人们会通过纯粹的运气而不是技巧来通过面试。这意味着那里的开发人员不能保证熟练,除非你可以教你的老年人技能,否则你可能会度过一段糟糕的时光。

于 2020-02-29T23:52:20.853 回答
-2
int a[] = {2,1,2,3,4};

int b[] = {0};

for(int i = 0; i < a.size; i++)
{

    if(a[i] == a[i+1])
    {
         //duplicate found
         //copy it to second array
        b[i] = a[i];
    }
}
于 2013-05-20T18:58:43.153 回答