ตรวจสอบว่าอาร์เรย์ประกอบด้วยจำนวนเต็มต่อเนื่องที่อนุญาตให้ทำซ้ำหรือไม่  


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ อเมซอน Directi Facebook ตรัสรู้
แถว กัญชา เชือก

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

ตัวอย่าง  

อินพุตตัวอย่าง:

[2, 3, 4, 1, 7, 9]

เอาต์พุตตัวอย่าง:

ใช่

คำอธิบาย:

มันมีชุดของจำนวนเต็มติดกันของจำนวน [2, 3, 4, 1]

อัลกอริทึมเพื่อตรวจสอบว่าอาร์เรย์มีจำนวนเต็มติดกันหรือไม่โดยอนุญาตให้มีการซ้ำกัน  

1. Declare a Set.
2. Add all the elements of an array into the Set.
3. Set count to 1 and currentElement to arr[0]-1.
4. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement--.
5. Set currentElement to arr[0]+1.
6. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement++.
7. Check if the count is equal to the size of a set, if condition satisfies, then return true.
8. Else return false.

คำอธิบาย  

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

ดูสิ่งนี้ด้วย
จะตรวจสอบได้อย่างไรว่าสองชุดที่กำหนดไม่ปะติดปะต่อกัน?

เราจะแทรกองค์ประกอบทั้งหมดโดยการข้ามอาร์เรย์เข้าไป ชุด และจะมีองค์ประกอบที่แตกต่างกันในตอนนี้ ตั้งค่าการนับเป็น 1 และเราจะเพิ่มขึ้นเรื่อย ๆ ในการดำเนินการในภายหลัง จะตรวจสอบขนาดของชุดที่ต่อเนื่องกันของจำนวนเต็มเนื่องจากจะมีขนาดที่แตกต่างจาก Set หากไม่มีจำนวนเต็มติดกันอยู่ในอาร์เรย์ arr [0] -1 จะเป็นค่าของ currentElement จะจับตาดูชุดของ จำนวนเต็ม.

เปิดลูปและมันจะดำเนินต่อไปจนกว่า Set จะมี currentElement อยู่ในนั้นเพราะในลูปเราจะเพิ่มมูลค่าของ count ทีละ 1 (count = count + 1) และลดค่าของ currentElement ลง 1 (currentElement = currentElement - 1). ตั้งค่าของ currentElement เป็น arr [0] +1 และเปิดอีกลูปหนึ่งและจะดำเนินต่อไปจนกว่า Set จะมี currentElement อยู่ แต่คราวนี้เราจะเพิ่มทั้งสองค่าโดย 1 count ++ และ currentElement ++ ในที่สุดเราจะตรวจสอบว่าค่าของ count เท่ากับขนาดของ Set หรือไม่หากพบว่าเป็นจริงให้คืนค่า true else return false

ให้เราพิจารณาตัวอย่าง:

ตัวอย่าง

arr [] = {5, 2, 3, 6, 4, 4, 6, 6};

หลังจากข้ามอาร์เรย์เราจะมีค่าต่อไปนี้ใน Set

ตั้งค่า: {2,3,4,5,6} เนื่องจากจะลบองค์ประกอบที่ซ้ำกัน

นับ = 1, currentElement = arr [0] -1 = 4;

  • ในขณะที่ Set มี currentElement (4) เป็นจริง

Count = count + 1 => count = 2, currentElement– => currentElement = 3

  • ในขณะที่ Set มี currentElement (3) เป็นจริง

Count = count + 1 => count = 3, currentElement– => currentElement = 2

  • ในขณะที่ Set มี currentElement (2) เป็นจริง
ดูสิ่งนี้ด้วย
ค้นหารายการที่ซ้ำกันในอาร์เรย์ที่กำหนดเมื่อองค์ประกอบไม่ จำกัด เฉพาะช่วง

Count = count + 1 => count = 4, currentElement– => currentElement = 1

  • ในขณะที่ Set มี currentElement (1) เป็นเท็จดังนั้นจึงออกมาจากลูป

ตั้งค่า currentElement [0] = arr [0] +1 => currentElement = 6

  • ในขณะที่ Set มี currentElement (6) เป็นจริง

Count = count + 1 => count = 5, currentElement ++ => currentElement = 7

  • ในขณะที่ Set มี currentElement (7) เป็นเท็จดังนั้นจึงออกมาจากลูป

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

การดำเนินงาน  

รหัส C ++ เพื่อตรวจสอบว่าอาร์เรย์มีจำนวนเต็มติดกันหรือไม่โดยอนุญาตให้มีการซ้ำกัน

#include<iostream>
#include<unordered_set>
using namespace std;
bool areElementsContiguous(int arr[], int n)
{
    unordered_set<int> Set;
    for (int i = 0; i < n; i++)
        Set.insert(arr[i]);

    int count = 1;
    int currentElement = arr[0] - 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement--;
    }
    currentElement = arr[0] + 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement++;
    }
    return (count == (int)(Set.size()));
}
int main()
{
    int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (areElementsContiguous(arr, n))
        cout << "Yes, it is set of contiguous integers.";
    else
        cout << "No, it is not a set of contiguous integers.";
    return 0;
}
Yes, it is set of contiguous integers.

รหัส Java เพื่อตรวจสอบว่าอาร์เรย์มีจำนวนเต็มติดกันหรือไม่โดยอนุญาตให้มีการซ้ำกัน

import java.util.HashSet;
class contiguousArray
{
    public static Boolean checkContiguousElements(int arr[], int n)
    {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            set.add(arr[i]);
        }
        int count = 1;
        int currentElement = arr[0] - 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement--;
        }
        currentElement = arr[0] + 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement++;
        }
        return (count == (set.size()));
    }
    public static void main(String[] args)
    {
        int arr[] = { 10, 7, 8, 11, 9, 9, 10, 10 };
        int n = arr.length;
        if (checkContiguousElements(arr, n))
            System.out.println("Yes, it is set of contiguous integers.");
        else
            System.out.println("No, it is not a set of contiguous integers.");
    }
}
Yes, it is set of contiguous integers.

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

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

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

ดูสิ่งนี้ด้วย
ผลรวมของ f (a [i], a [j]) เหนือทุกคู่ในอาร์เรย์ของจำนวนเต็ม n

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

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์