องค์ประกอบที่จะเพิ่มเพื่อให้องค์ประกอบทั้งหมดของช่วงมีอยู่ในอาร์เรย์


ระดับความยาก กลาง
ถามบ่อยใน สีเทาOrange คูลิซา Snapdeal Synopsys Teradata ไทม์อินเทอร์เน็ต
แถว กัญชา hashing การเรียงลำดับ

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

“ องค์ประกอบที่จะเพิ่มเพื่อให้องค์ประกอบทั้งหมดของช่วงอยู่ในอาร์เรย์” ระบุว่าคุณได้รับจำนวนเต็มอาร์เรย์ คำสั่งปัญหาขอให้ค้นหาจำนวนองค์ประกอบที่จะเพิ่มในอาร์เรย์เพื่อให้องค์ประกอบทั้งหมดอยู่ในช่วง [X, Y] โดยรวมอย่างน้อยหนึ่งครั้งในอาร์เรย์ X และ Y คือจำนวนต่ำสุดและสูงสุดของอาร์เรย์ตามลำดับ

ตัวอย่าง

arr[] = {4,5,7,9,11}
3

คำอธิบาย: X และ Y คือ 4 และ 11 (ตัวเลขต่ำสุดและสูงสุดตามลำดับ) ภายในช่วงของตัวเลขเหล่านี้มีเพียง 3 ตัวเท่านั้นที่หายไป 6, 8 และ 10

องค์ประกอบที่จะเพิ่มเพื่อให้องค์ประกอบทั้งหมดของช่วงมีอยู่ในอาร์เรย์

arr[] = {2,4,6,7}
2

คำอธิบาย: X และ Y คือ 2 และ 7 (ตัวเลขต่ำสุดและสูงสุดตามลำดับ) ภายในช่วงของตัวเลขเหล่านี้มีเพียง 2 เท่านั้นที่หายไป 3 และ 5

อัลกอริทึมเพื่อค้นหาองค์ประกอบที่จะเพิ่มเพื่อให้องค์ประกอบทั้งหมดของช่วงอยู่ในอาร์เรย์

1. Declare a Set.
2. Set output to 0, minValue to the maximum value of integer and maxValue to the minimum value of an integer.
3. Traverse the array and put all the values into the set and simultaneously find out the maximum and the minimum number of an array and store it to the maxValue and minValue respectively.
4. Traverse the array again, from minValue to maxValue.
5. Check if the map doesn’t contain any of the elements in traversal, then, increase the count of output.
6. Return output.

คำอธิบาย

เรามี จำนวนเต็ม อาร์เรย์ ปัญหาคือการหาจำนวนองค์ประกอบที่จะเพิ่มในอาร์เรย์ เพื่อให้องค์ประกอบทั้งหมดอยู่ในช่วงของจำนวนสูงสุดและต่ำสุดของอาร์เรย์เพื่อไม่ให้องค์ประกอบใด ๆ เกิดขึ้นอย่างน้อยหนึ่งครั้ง

ประกาศชุดชุดมีคุณสมบัติในการจัดเก็บองค์ประกอบที่แตกต่างกันเพียงครั้งเดียว ซึ่งหมายความว่าจะลบองค์ประกอบทั่วไปและจัดเก็บเฉพาะองค์ประกอบที่แตกต่างกัน ดังนั้นเราจะสามารถจัดการกับกรณีนั้นได้ ตอนนี้เราจะแทรกองค์ประกอบอาร์เรย์ทั้งหมดลงในชุด ในขณะเดียวกันเราจะหาองค์ประกอบสูงสุดและต่ำสุด เพื่อที่เราจะได้ไม่ต้องทำการสำรวจเพิ่มเติมเพื่อหาค่าสูงสุดและต่ำสุด ท้ายที่สุดเราก็ต้องหาจำนวนองค์ประกอบที่ขาดหายไปในช่วงนั้น ดังนั้นจึงมีความจำเป็นที่จะต้องนับจำนวนเท่านั้น และเราไม่ต้องจัดการกับตัวเลขด้วยตัวเอง

ตอนนี้เราจะข้ามอาร์เรย์โดยเริ่มจากค่าต่ำสุดในอาร์เรย์ไปจนถึงค่าสูงสุดของอาร์เรย์ เพราะนี่คือช่วงเดียวที่เราต้องการ เราจะเลือกตัวเลขแต่ละตัวภายในช่วงและตรวจสอบว่าชุดนั้นไม่มีค่าของช่วงนั้นหรือไม่ หากชุดนั้นไม่มีค่าช่วงปัจจุบันเราจะเพิ่มจำนวนเอาต์พุต และทุกครั้งเราจะเพิ่มมูลค่าของเอาต์พุตขึ้น 1 เมื่อใดก็ตามที่เราไม่มีค่าของช่วงอยู่ในชุด ราวกับว่าในรหัสที่กล่าวถึงต่ำสุดคือ 4 และสูงสุดคือ 11 และระหว่างนั้น 6,8 ถึง 10 จะขาดหายไปภายในช่วง (4,11) องค์ประกอบเหล่านี้จะไม่ปรากฏในอาร์เรย์ดังนั้นจะนับจำนวนองค์ประกอบนั้น และสุดท้ายเราจะส่งคืนผลลัพธ์นั้น

รหัส

รหัส C ++ เพื่อค้นหาองค์ประกอบที่จะเพิ่มเพื่อให้องค์ประกอบทั้งหมดของช่วงมีอยู่ในอาร์เรย์

#include<iostream>
#include<unordered_set>

using namespace std;

int getCountMissingNumber(int arr[], int n)
{
    unordered_set<int> SET;
    int output = 0;
    int maxValue = INT_MIN;
    int minValue = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        SET.insert(arr[i]);
        if (arr[i] < minValue)
            minValue = arr[i];
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    for (int a = minValue; a <= maxValue; a++)
    {
        if (SET.find(a) == SET.end())
        {
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {4,5,7,9,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getCountMissingNumber(arr, n);
    return 0;
}
3

โค้ด Java เพื่อค้นหาองค์ประกอบที่จะเพิ่มเพื่อให้องค์ประกอบทั้งหมดของช่วงอยู่ในอาร์เรย์

import java.util.HashSet;

class NumberBwRange
{
    public static int getCountMissingNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<>();
        int output = 0;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
            if (arr[i] < minValue)
                minValue = arr[i];
            if (arr[i] > maxValue)
                maxValue = arr[i];
        }

        for (int i = minValue; i <= maxValue; i++)
            if (!SET.contains(i))
                output++;
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 4,5,7,9,11 };
        int n = arr.length;
        System.out.println(getCountMissingNumber(arr, n));
    }
}
3

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (สูงสุด - นาที + 1) ที่ไหน “ สูงสุด” และ  "นาที" เป็น สูงสุด และ ขั้นต่ำ ค่าของอาร์เรย์ เนื่องจากเราข้ามจากองค์ประกอบขั้นต่ำไปยังองค์ประกอบสูงสุด นั่นเป็นเหตุผลว่าทำไมในกรณีที่เลวร้ายที่สุดค่านี้อาจเกิน N องค์ประกอบ ดังนั้นเนื่องจาก max-min + 1 อาจมากกว่า N ความซับซ้อนของเวลาคือ O (max-min + 1) โดยที่ max หมายถึงองค์ประกอบสูงสุดและ min หมายถึงองค์ประกอบขั้นต่ำ

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

บน) ที่ไหน “ N” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราจัดเก็บเฉพาะ N องค์ประกอบอัลกอริทึมจึงมีความซับซ้อนของพื้นที่เชิงเส้น