困惑：在数组找出重复的元素 [英] Puzzle : finding out repeated element in an Array

问题描述

数组的大小是数组中的元素n.Al​​l中的范围是不同的[0，N-1]但有两个elements.Find了重复的元素，而无需使用额外的临时数组恒定时间复杂度。

我试着用O（N）是这样的。

  A [] = {1,0,0,2,3};
    B〔] = { -  1，-1，-1，-1，-1};
    I = 0;
    INT要求;
    而（I＆LT; N）
    {
      苯并[a [i]] ++;
      如果（二[一由[i] == 1）
        需要= A [I]
    }
    打印要求;
 

如果没有对数字的范围没有限制，允许即超出范围also.Is有可能变成O（n）的解决方案，而临时数组。

解决方案

1. 看看什么是第一和最后一个数字


2. 计算SUM（1）不重复的数组元素（像你知道1 ... 5 = 1 + 2 + 3 + 4 + 5 = 15称它为SUM的那笔（1））。由于AaronMcSmooth指出，公式为总和（1，N）=（N + 1）N / 2 。


3. 计算SUM（2），它给你的数组中的元素的。


4. 减去SUM（2） - SUM（1）。哇！结果是重复的数目（例如，如果一个给定的阵列是1，2，3，4，5，3中，SUM（2）将18 18 - 15 = 3。因此3是重复的）。
   

好运编码！

Size of an array is n.All elements in the array are distinct in the range of [0 , n-1] except two elements.Find out repeated element without using extra temporary array with constant time complexity.

I tried with o(n) like this.

   a[]={1,0,0,2,3};
    b[]={-1,-1,-1,-1,-1};
    i=0;
    int required;
    while(i<n)
    {
      b[a[i]]++;
      if(b[a[i]==1)
        required=a[i];
    }
    print required;

If there is no constraint on range of numbers i.e allowing out of range also.Is it possible get o(n) solution without temporary array.

解决方案

1. Look what is first and last number
2. Calculate SUM(1) of array elements without duplicate (like you know that sum of 1...5 = 1+2+3+4+5 = 15. Call it SUM(1)). As AaronMcSmooth pointed out, the formula is Sum(1, n) = (n+1)n/2.
3. Calculate SUM(2) of the elements in array that is given to you.
4. Subtract SUM(2) - SUM(1). Whoa! The result is the duplicate number (like if a given array is 1, 2, 3, 4, 5, 3, the SUM(2) will be 18. 18 - 15 = 3. So 3 is a duplicate).

Good luck coding!

这篇关于困惑：在数组找出重复的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！