ค้นหาองค์ประกอบที่หายไปจากอาร์เรย์ที่ซ้ำกัน

คำชี้แจงปัญหา

เนื่องจากอาร์เรย์ 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 = (สูง + ต่ำ) / 2
4. ถ้า A [mid] = B [mid] ให้ค้นหาองค์ประกอบในส่วนที่ถูกต้องโดยทำให้ต่ำเป็นกลาง
5. มิฉะนั้นให้ค้นหาองค์ประกอบในส่วนด้านซ้ายโดยทำให้สูงถึงกลาง
6. สิ้นสุดลูปเมื่อ low = high - 1 และส่งคืน A [mid] ซึ่งเป็นองค์ประกอบที่ขาดหายไป

3. สร้างฟังก์ชันใหม่ FindMissing พร้อมเงื่อนไข:

1. ถ้า Size of A = Size of B + 1 ให้พิมพ์ FindMissingInB (A, B)
2. ถ้า Size of B = Size of 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

โปรแกรม 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 คือขนาดของอาร์เรย์ ที่นี่เราใช้ a ค้นหาไบนารี ซึ่งนำเราไปสู่ความซับซ้อนของเวลาเข้าสู่ระบบ

ความซับซ้อนของอวกาศ

O (1) เพราะเราใช้ตัวแปรเพียงไม่กี่ตัวเพื่อค้นหาคำตอบ

แนวทาง 2

ขั้นตอนวิธี

หากองค์ประกอบในอาร์เรย์ไม่อยู่ในลำดับเดียวกัน

1. เราสร้างไฟล์ ฟังก์ชัน FindMissing เพื่อค้นหาองค์ประกอบที่ขาดหายไป

2. ในฟังก์ชั่นนี้:

1. เริ่มต้น Missing_element = 0
2. ใช้ XOR กับองค์ประกอบทั้งหมดในอาร์เรย์ด้วย Missing_element
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

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

คำถามสัมภาษณ์ยอดนิยม