具有k个不同数字的最小子数组


难度级别
经常问 亚马逊 谷歌
排列 哈希 滑动窗口 两指针

假设您有一个整数 排列 还有一个数字k 问题陈述要求找出包含范围(l,r)的最小子数组,以这种方式,在该最小子数组中恰好存在k个不同的数字。

使用案列

输入:

{1,2,2,3,4,5,5}

k = 3

输出:

2,4

说明:

{2,3,4}是从2开始的最小子数组nd 索引到4th 带有k的索引,即3个不同的元素。

输入:

{2,5,6,7}

k = 2

输出:

2,3

说明:

{2,5}是从第二索引到第三索引的最小子数组,具有k,即2个不同的元素。

算法

  1. 将distinct元素设置为0,并将左侧和右侧指针设置为-1。
  2. 遍历数组,
  3. 如果没有不同元素的个数小于给定数k,则将右边增加1。
  4. 然后增加计数并将数组元素的频率存储到 地图.
  5. 如果不同的元素等于给定的数字k,并且所形成的长度小于以前更新的长度,则左侧和右侧指针会中断。
  6. 如果发现不同元素的数量小于k,则中断。
  7. 检查发现不同元素的数量是否等于k,然后增加右侧指针。
  8. 如果不同的元素等于给定的数字k,并且所形成的长度小于以前更新的长度,则左侧和右侧指针会中断。
  9. 检查是否发现该元素的频率为1,然后从地图中删除该元素,否则减少该元素的频率计数
  10. 如果发现左侧指针为0,右侧指针等于n,则表示该指针无效。
  11. 否则,打印左侧和右侧的值。

说明

在遍历数组时存储每个数组元素的频率,并选择每个数组元素,并检查映射大小是否小于k,如果发现小于k,则小于我们需要计算和存储该数组元素的频率,以及映射大小被发现为k(不同的元素编号),并且当前长度小于子数组的先前长度,那么我们将更新左侧和右侧指针。 这一切将循环进行,直到遍历整个地图一次。

如果发现地图的大小小于k,则断开。 我们在地图上得到了值。 循环将一直进行到找到映射的大小等于k,找到映射中数组元素的频率等于1,然后我们需要从映射中删除该特定元素,否则需要减小映射的大小。地图中该特定元素的频率。 再次,我们将检查映射大小是否等于k并且当前子数组的长度小于先前更新的长度,然后更新左侧和右侧指针。 如果数组元素的频率为1,则删除该元素,否则降低该元素的频率。

遍历数组后,如果发现左侧指针为0,右侧指针为n,则表示它是无效的k。 否则,将打印左侧和右侧指针的值,该值将是最小子数组的起点和终点。

实施

具有k个不同数字的最小子数组的C ++程序#include

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}
2 4

具有k个不同数字的最小子数组的Java程序

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}
2 4

具有k个不同数字的最小子数组的复杂度分析

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。