查找1到N-1之間的唯一重複元素


難度級別 容易獎學金
經常問 優惠券 德里韋里 灰色橙色 信息邊緣 LinkedIn 長郎 SAP實驗室
排列 哈希 搜索

在找到1到N-1問題之間的唯一重複元素時,我們給出了 排列 在1到n-1範圍內的隨機整數。 將重複一個數字。 您的任務是找到該號碼。

輸入

[2,3,4,5,2,1] A

產量

2

解釋

2是在數組中出現兩次的元素。

 

查找介於1到N-1之間的唯一重複元素的算法

  1. 將總和設置為0。
  2. 當i <n時,遍歷整個數組。
    1. Sum = sum + arr [i]。
  3. 返回sum-(n *(n-1))/ 2。

查找1到N-1之間的唯一重複元素的說明

我們給出了一個問題(查找1到N-1之間的唯一重複元素),該語句要求找出在數組中重複的數字。 我們將簡單地使用 求和公式。 運用 求和公式, 我們可以輕鬆地識別出重複元素。 就像名字一樣,我們知道 求和公式 就是簡單地將這些值相加。

我們在循環中從這裡的第0個位置開始遍歷數組,直到循環的最後,直到我們訪問最後一個數組元素。 對於每次迭代,對於array [i]的每個值,我們將其與sum相加並將其存儲到sum中,以便下次迭代時將獲得sumsum的值,而不是sum的初始化值,如0。因此,每次迭代,我們都會在其中存儲一些總和值。

我們只需要製作一個給出重複元素的公式,或者可以說它只是返回該系列中包含的一個額外元素。 假設我們有一個從1到5連續給出的序列,當我們將所有數字相加時,它給出了所有數字的總和,並且在序列中沒有任何重複的元素。 然後我們返回總和的差–(n *(n-1))/ 2,這是我們的總和公式。

讓我們考慮一個例子:

arr = [2,3,4,5,2,1],sum = 0

從0開始,我們可以遍歷訪問每個元素的整個循環–>

i = 0;

sum = sum + arr [i] => sum = 2

i = 1;

sum = sum + arr [i] => sum = 5

i = 2;

sum = sum + arr [i] => sum = 9

i = 3;

sum = sum + arr [i] => sum = 14

i = 4;

sum = sum + arr [i] => sum = 16

i = 5;

sum = sum + arr [i] => sum = 17

然後我們只返回sum-(n *(n-1))/ 2,即17-(6 *(6-1))/ 2。

17 – 15 = 2,這是我們所需的輸出。

 

查找1到N-1之間的唯一重複元素

查找介於1到N-1之間的唯一重複元素的實現

C ++程序

#include<iostream>
using namespace std;
int getRepeatedElement(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = sum + arr[i];
    }
    return sum-(((n - 1) * n)/2);
}
int main()
{
    int arr[] = {1,5,3,2,6,4,7,8,4};
    int len = sizeof(arr)/sizeof(arr[0]);
    cout<<(getRepeatedElement(arr, len));
    return 0;
}
4

Java程序

class repetitiveElement
{
    public static int getRepeatedElement(int[] arr, int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum = sum + arr[i];
        }
        return sum-(((n - 1) * n)/2);
    }
    public static void main(String args[])
    {
        int[] arr = {1,5,3,2,6,4,7,8,4};
        int len = arr.length;
        System.out.println(getRepeatedElement(arr, len));
    }
}
4

複雜性分析以查找1到N-1之間的唯一重複元素

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。

空間複雜度

O(1) 因為我們在這裡不使用任何輔助空間。

參考