最长子数组不超过K个不同元素


难度级别 中等
经常问 亚马逊 堡垒 德里韦里 Facebook 微软 Samsung Yandex的
排列 哈希 滑动窗口

问题“最长的子数组不超过K个不同的元素”表示您有一个 排列 of 整数,问题陈述要求找出最长不超过k个不同元素的子数组。

使用案列最长子数组不超过K个不同元素

arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5}
k=3
2, 1, 2, 0

说明

具有k个不同元素的最长子数组(2,1,2,0)

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

说明

具有k个不同元素的最长子数组(3,4)

算法

  1. 增加并保留每个元素的数量
  2. 从0开始,保持不同元素的计数,直到它大于k。
  3. 如果计数大于k,则开始减少元素数(起点)。
  4. 继续删除计数,直到我们再次得到k个不同的元素,也增加了子数组的起点。
  5. 通过检查最长子数组长度,根据数组元素索引更新末尾。
  6. 从终点开始打印数组形式。

说明

我们给出了一个整数数组,我们要求找出一个数组中存在的最长子数组,该数组中最多有k个不同的元素。 我们将使用类似的方法 散列。 尽管我们需要找到最长的子数组,但我们必须继续增加每个元素的数量。 因此,我们必须关注子数组的起点和子数组的终点。 因此,我们将从头到尾打印给我们的子数组不超过k个不同的元素。

我们还必须保持该事物的计数,以确保任何数字都不应超过k。 让我们举个例子:

Arr [] = {4,3,5,2,1,2,0,4,5},k = 3

我们选择数组的每个元素并增加一个数组元素的计数,每次我们检查它是否是第一次出现时,我们都会增加当前计数,我们将其与k进行比较,而不是任何东西,直到它变得大于k。 如果它大于k,我们将从0开始减少元素的数量,并增加该值,以便下次我们可以减少下一个元素的数量。 我们应该增加left的值,它将成为子数组的起点,直到我们再次找到k个不同的元素。

如果我们考虑数组中的4、3和5,则我有i = 2,curr = 3,如果我们转到下一个元素,我们得到的curr为4,我们得到2作为子数组的起点,我们应该保持直到找到超过k个不同的元素。

代码

C ++代码查找最长不超过K个不同元素的子数组

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

void getLongestSub(int arr[], int n, int k)
{
    unordered_map<int, int> count;

    int start = 0, endp = 0, curr = 0, left = 0;
    for (int i = 0; i < n; i++)
    {
        count[arr[i]]++;
        if (count[arr[i]] == 1)
            curr++;
        while (curr > k)
        {
            count[arr[left]]--;

            if (count[arr[left]] == 0)
                curr--;

            left++;
        }
        if (i - left + 1 >= endp - start + 1)
        {
            endp = i;
            start = left;
        }
    }
    for (int i = start; i <= endp; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getLongestSub(arr, n, k);
    return 0;
}
2 1 2 0

Java代码查找最长不超过K个不同元素的子数组

import java.util.*;

class longestSubArray
{
    public static void getLongestSub(int arr[], int n, int k)
    {
        int[] count = new int[7];
        int start = 0, end = 0, curr = 0, left = 0;
        for (int i = 0; i < n; i++)
        {
            count[arr[i]]++;
            if (count[arr[i]] == 1)
                curr++;

            while (curr > k)
            {
                count[arr[left]]--;

                if (count[arr[left]] == 0)
                    curr--;
                left++;
            }
            if (i - left + 1 >= end - start + 1)
            {
                end = i;
                start = left;
            }
        }
        for (int i = start; i <= end; i++)
            System.out.print(arr[i]+" ");
    }
    public static void main(String args[])
    {
        int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
        int n = arr.length;
        int k = 3;
        getLongestSub(arr, n, k);
    }
}
2 1 2 0

复杂度分析

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 使用哈希图使我们可以在O(1)时间内插入,删除和搜索。 因此,时间复杂度是线性的。

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 在最坏的情况下,我们可能必须存储所有元素。 因此,空间复杂度也是线性的。