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


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน Avalara ป้อมปราการ ฟรีค่าธรรมเนียม HackerRank Snapchat Snapdeal
แถว กัญชา

ปัญหา "ตรวจสอบว่าอาร์เรย์ที่ระบุมีองค์ประกอบที่ซ้ำกันภายในระยะ k จากกันหรือไม่" ระบุว่าเราต้องตรวจสอบรายการที่ซ้ำกันในอาร์เรย์ที่ไม่ได้เรียงลำดับที่กำหนดภายในช่วง k ที่นี่ค่าของ k มีขนาดเล็กกว่าอาร์เรย์ที่กำหนด

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

ตัวอย่าง

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

คำอธิบาย

เรามีสองวิธีในการแก้ปัญหานี้ วิธีที่ง่ายกว่าคือการเรียกใช้สองลูปซึ่งลูปแรกจะเลือกทุกองค์ประกอบเป็นองค์ประกอบเริ่มต้นสำหรับ 'วงใน' วงที่สอง หลังจากนั้นลูปที่สองจะเปรียบเทียบองค์ประกอบเริ่มต้นกับองค์ประกอบทั้งหมดที่อยู่ในช่วง "k" แต่การแก้ปัญหานี้ไม่ได้มีประสิทธิภาพนั้นต้องใช้เวลากับความซับซ้อนของ O (k * n)

แต่เรามีอีกวิธีหนึ่งที่มีประสิทธิภาพมากกว่าซึ่งสามารถแก้ปัญหาได้ O (n) ความซับซ้อนของเวลาที่เรียกว่า hashing. ในวิธีการแฮชเราจะสำรวจองค์ประกอบทั้งหมดของอาร์เรย์และเราจะตรวจสอบว่ามีองค์ประกอบอยู่ในนั้นหรือไม่ หากองค์ประกอบอยู่ในนั้นเราจะคืนค่า 'True' มิฉะนั้นเราจะเพิ่มมันลงในแฮชและลบองค์ประกอบ arr [ik] ออกจากแฮชถ้า 'i' มากกว่าหรือเท่ากับ 'k'

อัลกอริทึมเพื่อตรวจสอบว่าอาร์เรย์ที่กำหนดมีองค์ประกอบที่ซ้ำกันภายในระยะ k จากกันหรือไม่

  1. ขั้นแรกให้สร้างช่องว่าง ชุดแฮช ซึ่งเราจะจัดเก็บองค์ประกอบของอาร์เรย์
  2. สำรวจองค์ประกอบทั้งหมดของอาร์เรย์จากซ้ายไปขวา
  3. ตรวจสอบว่ามีองค์ประกอบอยู่ในแฮชหรือไม่
    • ถ้าอยู่ในนั้นให้ส่งกลับ "จริง"
    • เพิ่มองค์ประกอบนั้นลงในแฮช
  4. หลังจากนั้นให้ลบองค์ประกอบ arr [ik] ออกจากแฮชถ้า 'I' มากกว่าหรือเท่ากับ 'k'

 

เรามีอาร์เรย์ 'arr []' ที่มีองค์ประกอบบางอย่างอยู่ในนั้นและค่า k ซึ่งเป็นช่วงที่เราต้องหารายการที่ซ้ำกันหากมีดังนั้นจะใช้ชุดแฮชเพื่อเก็บองค์ประกอบในนั้นก่อนเราจะเพิ่มองค์ประกอบของ อาร์เรย์ในแฮชของเราตั้งค่าทีละรายการหากองค์ประกอบอยู่ในชุดแฮชแล้วมันจะคืนค่าจริงและทำลายลูปมิฉะนั้นจะแทรกองค์ประกอบในชุดอย่างต่อเนื่องและลบองค์ประกอบ arr [ik] ออกจากชุด

รหัส

รหัส C ++ เพื่อตรวจสอบว่าอาร์เรย์ที่ระบุมีองค์ประกอบที่ซ้ำกันภายในระยะ k จากกันหรือไม่

#include<iostream>
#include<unordered_set>
using namespace std;

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

    for (int i = 0; i < n; i++)
    {
        if (D_set.find(a[i]) != D_set.end())
            return true;

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}
Yes

รหัส Java เพื่อตรวจสอบว่าอาร์เรย์ที่กำหนดมีองค์ประกอบที่ซ้ำกันภายในระยะ k จากกันหรือไม่

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

    public static void main (String[] args)
    {
        int a[] = {1, 2, 3, 4, 1};
        int k = 5;

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

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

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

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ การใช้ชุดแฮชช่วยให้แก้ปัญหาได้ในเวลาเชิงเส้น เนื่องจากการใช้ชุดแฮชช่วยเพิ่มความสามารถในการค้นหาลบและแทรกข้อมูลได้อย่างมีประสิทธิภาพ

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

ตกลง) ที่ไหน "K" คือจำนวนองค์ประกอบในหน้าต่างที่ต้องพิจารณา