นับ subarrays ที่มีองค์ประกอบที่แตกต่างกันทั้งหมดเหมือนกับอาร์เรย์ดั้งเดิม


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน Databricks Fab Honeywell payu สี่เหลี่ยมด้านเท่า Teradata Yandex
แถว กัญชา hashing หน้าต่างบานเลื่อน

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

“ นับ subarrays ที่มีองค์ประกอบที่แตกต่างกันทั้งหมดเหมือนกับต้นฉบับ แถว” ระบุว่าคุณได้รับอาร์เรย์จำนวนเต็ม คำสั่งปัญหาจะขอให้ค้นหาจำนวนอาร์เรย์ย่อยทั้งหมดที่มีองค์ประกอบที่แตกต่างกันทั้งหมดตามที่มีอยู่ในอาร์เรย์ดั้งเดิม

ตัวอย่าง

arr[] = {2, 1, 3, 2, 3}
5

คำอธิบาย: อาร์เรย์ย่อย⇒ {2, 1, 3}, {1, 3, 2}, {1, 3, 2, 3}, {2, 1, 3, 2} และ {2, 1, 3, 2 , 3} มีองค์ประกอบที่แตกต่างกันทั้งหมดเป็นอาร์เรย์ดั้งเดิม

นับ subarrays ที่มีองค์ประกอบที่แตกต่างกันทั้งหมดเหมือนกับอาร์เรย์ดั้งเดิม

arr[] = {2, 4, 3, 4, 1, 2}
4

คำอธิบาย: อาร์เรย์ย่อย⇒ {3, 4, 1, 2}, {4, 3, 4, 1, 2}, {2, 4, 3, 4, 1} และ {2, 4, 3, 4, 1 , 2} มีองค์ประกอบที่แตกต่างกันทั้งหมดเป็นอาร์เรย์ดั้งเดิม

อัลกอริทึมในการนับอาร์เรย์ย่อยที่มีองค์ประกอบที่แตกต่างกันทั้งหมดเหมือนกับอาร์เรย์ดั้งเดิม

1. Declare a map.
2. Add all the values of array into the map with 1 as each key’s value.
3. Find the size of the map, store it to k and clear the map.
4, Set output, right, and maxsa to 0.
5. Traverse the array, from i=0, to i < n(length of the array).
  1. While the right is less than n and maxsa is less than k,
    1. Insert arr[right] and increase its frequency by 1.
    2. Check if the map’s value of current array element (arr[right]) is equal to 1 if true then increase the count of maxsa by 1.
  2. Increase the count of right by 1.
  3. If maxsa is equal to k, then update output à output += (n - right + 1).
  4. Insert the value of current arr[left] and decrease its frequency by 1.
  5. If the map’s arr[left] is equal to 0, then decrease the value of maxsa by 1.
6. Return output.

คำอธิบาย

เราได้ให้ไฟล์ จำนวนเต็ม อาร์เรย์เราถูกขอให้ค้นหาจำนวนอาร์เรย์ย่อยทั้งหมดที่มีองค์ประกอบที่แตกต่างกันทั้งหมดตามที่มีอยู่ในอาร์เรย์ดั้งเดิม สำหรับสิ่งนี้เราจะใช้ hashing. เป็นแนวทางที่มีประสิทธิภาพในการแก้ปัญหารหัสนี้

ประกาศก แผนที่. เราจะสำรวจอาร์เรย์ทั้งหมดและใส่แต่ละองค์ประกอบลงในแผนที่โดยมีความถี่เท่ากับ 1 เท่านั้นเนื่องจากเราไม่ต้องการนับความถี่ของแต่ละองค์ประกอบ นี่เป็นเพียงเพื่อให้ทราบว่ามีคีย์เฉพาะจำนวนเท่าใดในอาร์เรย์ที่กำหนด เราจะจัดเก็บขนาดของแผนที่ลงในตัวแปร k และล้างแผนที่

เราจะสำรวจอาร์เรย์ทั้งหมด แต่ก่อนหน้านั้นเราตั้งค่าของผลลัพธ์ทางขวาและ maxsa เป็น 0 เริ่มจาก 0 เราจะป้อนซ้ำอีกครั้งในการค้นหาอาร์เรย์ย่อยในขณะที่ทางขวามีค่าน้อยกว่า n และ maxsa น้อยกว่า k ตอนนี้เราจะใส่องค์ประกอบอาร์เรย์และเพิ่มความถี่ทีละ 1 เราจะตรวจสอบว่าองค์ประกอบปัจจุบันมีความถี่เป็น 1 หรือเราเพิ่งอัปเดตให้มากขึ้นหากพบว่าเป็นจริงให้เพิ่มค่า ของ maxsa

หลังจากออกมาจาก ในขณะที่วนซ้ำคุณจะมีค่า maxsa ที่เพิ่มขึ้นหากมีค่าเท่ากับ k จากนั้นอัปเดตผลลัพธ์เป็น n-right +1 ในขณะที่เราใส่ค่าขององค์ประกอบอาร์เรย์ลงในแผนที่แล้ว ตอนนี้เราจะลดความถี่ลง 1 และตรวจสอบว่าค่า arr [left] เท่ากับ 0 หรือไม่และลดค่า maxsa เมื่อใดก็ตามที่เราพบค่าของ maxsa ถึง k เราจะอัปเดตค่าผลลัพธ์

รหัส

รหัส C ++ เพื่อนับ subarrays ที่มีองค์ประกอบที่แตกต่างกันทั้งหมดเหมือนกับอาร์เรย์ดั้งเดิม

#include<iostream>
#include<unordered_map>

using namespace std;

int getSubArrayDistinct(int arr[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[arr[i]] = 1;

    int k = MAP.size();

    MAP.clear();

    int output = 0, right = 0, maxsa = 0;
    for (int left = 0; left < n; ++left)
    {
        while (right < n && maxsa < k)
        {
            ++MAP[ arr[right] ];

            if (MAP[ arr[right] ] == 1)
                ++maxsa;

            ++right;
        }
        if (maxsa == k)
        {
            output += (n - right + 1);
        }
        --MAP[ arr[left] ];

        if (MAP[ arr[left] ] == 0)
        {
            --maxsa;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 1, 3, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getSubArrayDistinct(arr, n);
}
5

โค้ด Java เพื่อนับ subarrays ที่มีองค์ประกอบที่แตกต่างกันทั้งหมดเหมือนกับอาร์เรย์ดั้งเดิม

import java.util.HashMap;

class SubarrayWithDistinctEle
{
    public static int getSubArrayDistinct(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>()
        {
            @Override
            public Integer get(Object key)
            {
                if(!containsKey(key))
                    return 0;
                return super.get(key);
            }
        };

        for (int i = 0; i < n; ++i)
            MAP.put(arr[i], 1);
        int k = MAP.size();

        MAP.clear();

        int output = 0, right = 0, maxsa = 0;
        for (int left = 0; left < n; ++left)
        {
            while (right < n && maxsa < k)
            {
                MAP.put(arr[right], MAP.get(arr[right]) + 1);

                if (MAP.get(arr[right])== 1)
                {
                    ++maxsa;
                }

                ++right;
            }
            if (maxsa == k)
            {
                output += (n - right + 1);
            }

            MAP.put(arr[left], MAP.get(arr[left]) - 1);

            if (MAP.get(arr[left]) == 0)
                --maxsa;
        }
        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2, 1, 3, 2, 3};
        int n=arr.length;
        System.out.println(getSubArrayDistinct(arr, n));
    }
}
5

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

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

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

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

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