從重複數組中查找丟失的元素  


難度級別 容易獎學金
經常問 ol石 土磚 亞馬遜 蘋果 彭博社 第一資本 思科 易趣 Facebook 高盛 谷歌 IBM JP摩根 Microsoft微軟 Nvidia公司 神諭 貝寶 的ServiceNow Yandex的
Arista Networks 排列 哈希 哈希

問題陳述  

給定兩個數組A和B,一個數組是另一個數組的重複,除了一個元素。 A或B中缺少一個元素。我們需要從重複的元素中找到丟失的元素 排列.

例  

5
1 6 4 8 9
6 4 8 9
1

方法1  

算法

如果元素的順序相同,

1. 創建一個函數FindMissingInB,其中A的大小大於B的大小,這意味著B中缺少該元素。

2. 在FindMissingInB函數中:

  1. 如果數組A中只有一個元素,則B中缺少該元素,請返回該元素。
  2. 如果第一個元素在A和B中不相等,則缺少第一個元素本身,則返回A的第一個元素。
  3. 否則,將中和低初始化為數組A的拐角點,並在數組A中開始二進制搜索,並獲得mid =(high + low)/ 2。
  4. 如果A [mid] = B [mid],則將中值設為低,在右側部分中搜索元素。
  5. 否則,通過將中點設為高來在左側部分中搜索元素。
  6. 當低=高– 1時,結束循環,並返回A [mid],這是缺少的元素。
也可以看看
猜猜這個單詞

3. 使用條件創建一個新函數FindMissing:

  1. 如果A的大小= B的大小+ 1,則打印FindMissingInB(A,B)
  2. 如果B的大小= A的大小+ 1,則打印FindMissingInB(B,A)
  3. 否則,輸入無效。

4. 在給定的兩個輸入數組上調用該函數以打印缺少的數字。

履行

C ++程序,用於從重複數組中查找丟失的元素

#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
//Function:
//Using binary search approch in finding the missing element
//where A[] is bigger array than B
//Assuming the elements in same order in both A and B
int FindMissingInB(int A[], int B[], int N)
{
    //condition
    //only one element in A and B is empty
    if (N == 1)
        {
            return A[0];
        }
    //condition
    //First element is missing
    // special case, for first element missing
    if (A[0] != B[0])
        {
            return A[0];
        }
    //condition
    //element is in between  
    // Initialize low and high 
    int low = 0,high = N - 1;
    while (low < high)
    {
        int mid = (low + high) / 2;
        //mid elements are equal then search in right subarray
        if (A[mid] == B[mid])
            {
                low = mid;
            }
        else //mid elements are not eqaul 
            {
                high = mid;
            }
        // end when low = high -1
        if (low == high - 1)
            {
                break;
            }
    }
    //Missing element
    return A[high];
}
 
//Checking conditions Size A > Size B or 
void FindMissing(int A[], int B[], int M, int N)
{
    if (N == M-1)
    {
           cout << "Missing Element: "<< FindMissingInB(A, B, M) << endl;
    }
    else if (M == N-1)
    {
           cout << "Missing Element: "<< FindMissingInB(B, A, N) << endl;
    }
    else
    {
           cout << "Invalid!"<<endl;
    }
}
//Main Function
int main()
{
    int A[] = {1, 6, 4, 8, 9};
    int B[] = {6, 4, 8, 9};
    int M = sizeof(A)/sizeof(int);
    int N = sizeof(B)/sizeof(int);
    FindMissing(A, B, M, N);
    return 0;
}
Missing Element: 1

備註: 假設A和B數組中的元素順序相同。

也可以看看
輪換名單Leetcode解決方案

Java程序,用於從重複數組中查找丟失的元素

import java.util.Scanner;
class sum
{
    //Function:
    //Using binary search approch in finding the missing element
    //where A[] is bigger array than B
    //Assuming the elements in same order in both A and B
    public static int FindMissingInB(int A[], int B[], int N)
    {
        //condition
        //only one element in A and B is empty
        if (N == 1)
            {
                return A[0];
            }
        //condition
        //First element is missing
        // special case, for first element missing
        if (A[0] != B[0])
            {
                return A[0];
            }
        //condition
        //element is in between  
        // Initialize low and high 
        int low = 0,high = N - 1;
        while (low < high)
        {
            int mid = (low + high) / 2;
            //mid elements are equal then search in right subarray
            if (A[mid] == B[mid])
                {
                    low = mid;
                }
            else //mid elements are not eqaul 
                {
                    high = mid;
                }
            // end when low = high -1
            if (low == high - 1)
                {
                    break;
                }
        }
        //Missing element
        return A[high];
    }

    //Checking conditions Size A > Size B or 
    public static void FindMissing(int A[], int B[], int M, int N)
    {
        if(N == M-1)
        {
            System.out.println("Missing Element: " + FindMissingInB(A, B, M));
        }
        else if(M == N-1)
        {
            System.out.println("Missing Element: " + FindMissingInB(B, A, N));
        }
        else
        {
            System.out.println("Invalid!");
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[m];
        for(int i=0;i<m;i++)
        {
            b[i] = sr.nextInt();
        }
        FindMissing(a,b,n,m); 
    }
}
5
1 6 7 3 2
1 6 7 2
3

從重複數組中查找丟失元素的複雜度分析

時間複雜度

O(登錄) 其中n是數組的大小。 在這裡我們應用 二進制搜索 這導致我們登錄時間變得很複雜。

空間複雜度

O(1) 因為我們僅使用一些變量來找到解決方案。

也可以看看
重新排列數組,以使偶數索引元素較小而奇數索引元素較大

方法2  

算法

如果數組中的元素順序不同,

1. 我們創建一個 功能 FindMissing查找缺少的元素。

2. 在此功能中:

  1. 初始化Missing_element = 0
  2. 對Missing_element數組中的所有元素使用XOR
  3. 所有元素的Missing_element = Missing_element ^ A [i]或B [i]。

3. Missing_element的最終值是丟失的丟失元素。

4. 調用給定數組上的函數以打印缺少的元素。

C ++程序,用於從重複數組中查找丟失的元素

#include <bits/stdc++.h>
using namespace std;
 
//using XOR on all the elements.
void FindMissing(int A[], int B[], int M,int N)
{
    if (M != N-1 && N != M-1)
    {
        cout << "Invalid!";
        return;
    }
    int MissingElement = 0;
    for (int i=0; i<M; i++)
        {
            MissingElement = MissingElement^A[i];
        }
    for (int i=0; i<N; i++)
       {
            MissingElement = MissingElement^B[i];
       }
    cout << "Missing element: " << MissingElement;
}
 
//main function
int main()
{
    int A[] = {4, 1, 5, 9, 7};
    int B[] = {7, 5, 9, 4};
    int M = sizeof(A)/ sizeof(int);
    int N = sizeof(B)/ sizeof(int);
    FindMissing(A, B, M, N);
    return 0;
}
Missing element: 1

Java程序,用於從重複數組中查找丟失的元素

import java.util.Scanner;
class sum
{
    public static void FindMissing(int A[], int B[], int M,int N)
    {
    if (M != N-1 && N != M-1)
    {
        System.out.println("Invalid!");
        return;
    }
    int MissingElement = 0;
    for (int i=0; i<M; i++)
        {
            MissingElement = MissingElement^A[i];
        }
    for (int i=0; i<N; i++)
       {
            MissingElement = MissingElement^B[i];
       }
    System.out.println("Missing element: " + MissingElement);
}
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[m];
        for(int i=0;i<m;i++)
        {
            b[i] = sr.nextInt();
        }
        FindMissing(a,b,n,m); 
    }
}
3 2
1 2 3
1 2
3

從重複數組中查找丟失元素的複雜度分析

時間複雜度

O(N) 其中n是數組的大小。 在這裡,我們將數組精確遍歷一次,這意味著時間複雜度將為O(n)。

也可以看看
在k名學生中平均分配的最大巧克力數量

空間複雜度

O(1) 因為我們僅使用一些變量來找到解決方案。

參考