ประกอบด้วย Duplicate II Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน Facebook Google
แถว hashing หน้าต่างบานเลื่อน

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

ในปัญหานี้เราจะได้รับไฟล์ แถว จำนวนเต็มและเราต้องตรวจสอบว่ามีองค์ประกอบที่ซ้ำกันซึ่งอยู่ในระยะห่างอย่างน้อยหรือไม่ k ซึ่งกันและกัน.
กล่าวคือความแตกต่างระหว่างดัชนีของทั้งสององค์ประกอบเดียวกันควรน้อยกว่าเท่ากับ k
หรือ  จำนวน [i] == จำนวน [j] และ เอบีเอส (ij) <= k

ตัวอย่าง

nums = [1,2,3,1], k = 3
true

คำอธิบาย:

องค์ประกอบที่ดัชนี 0 และ 3 เหมือนกันและ 3 - 0 <= k

nums = [1,2,3,1,2,3], k = 2
false

แนวทางที่ 1 (Brute Force)

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

ขั้นตอนวิธี

  1. เรียกใช้ลูปสำหรับทุกองค์ประกอบ จำนวน [i] ของอาร์เรย์ที่กำหนด
  2. ภายในลูปนี้อีกครั้งเรียกใช้สำหรับลูปและสำรวจองค์ประกอบทั้งหมดจาก j = i + 1 ไปยัง j = i + k และเปรียบเทียบมูลค่ากับไฟล์ จำนวน [i]
    • If จำนวน [j] == จำนวน [i] จากนั้นคืนค่าจริง ตามที่เราได้พบองค์ประกอบ
  3. สุดท้ายเมื่อไม่พบองค์ประกอบที่ซ้ำกันให้คืนค่าเท็จก่อนออกจากฟังก์ชัน

การใช้งานสำหรับโซลูชัน Leetcode ที่มี Duplicate II

โปรแกรม C ++

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    for(int i=0;i<nums.size();i++)
        for(int j=i+1;j<nums.size() && j<=i+k;j++)
        {
            if(nums[j]==nums[i])
                return true;
        }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

โปรแกรม Java

class Rextester{
    
    public static boolean containsNearbyDuplicate(int[] nums, int k) 
    {
        for(int i=0;i<nums.length;i++)
            for(int j=i+1;j<nums.length && j<=i+k;j++)
            {
                if(nums[j]==nums[i])
                    return true;
            }

        return false;

    }
    
    public static void main(String args[])
    {
       	int[] nums={1,2,3,1};
        int k=3;
        System.out.println(containsNearbyDuplicate(nums,k) );
    }
}
true

การวิเคราะห์ความซับซ้อนสำหรับโซลูชัน Leetcode ที่มี Duplicate II

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

O (n * นาที (k, n)): เรากำลังสำรวจองค์ประกอบ min (k, n) สำหรับทุกองค์ประกอบของอาร์เรย์ ดังนั้นความซับซ้อนของเวลาจะเป็น O (n * min (k, n))

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

O (1): พื้นที่คงที่

แนวทางที่ 2 (หน้าต่างบานเลื่อน)

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

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

ดูตัวอย่างในรูปด้านล่าง:

ประกอบด้วย Duplicate II Leetcode Solution

ขั้นตอนวิธี

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

การใช้งานสำหรับโซลูชัน Leetcode ที่มี Duplicate II

โปรแกรม C ++

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

โปรแกรม Java

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

การวิเคราะห์ความซับซ้อนสำหรับโซลูชัน Leetcode ที่มี Duplicate II

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

บน) : เมื่อเราเข้าชมแต่ละองค์ประกอบเพียงครั้งเดียวและสมมติว่าการเพิ่มองค์ประกอบและการลบองค์ประกอบจะใช้เวลาคงที่ในความซับซ้อนของเวลาที่ตั้งแฮชลดลงเหลือเพียง O (n)

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

O (นาที (k, n)): เรากำลังจัดเก็บองค์ประกอบ k ไว้ที่สูงสุดในชุดแฮช ถ้า k> n จะมีเพียง n องค์ประกอบเท่านั้นที่จะถูกเก็บไว้ในชุดที่ค่าสูงสุด