K个空插槽


难度级别
经常问 亚马逊 谷歌
排列 有序地图

K个空槽正确地呈现了园丁的困境,试图挑选适合我们条件的花朵。

我们的园丁有N槽田。 园丁先生在每个插槽中都种了一朵花。 每朵花都会在某个花朵上绽放 独特 日。 此外,我们还种植了常绿的花。 一旦开花,它们就是 考虑 怒放 永远。

这些花中的每一个开花的日期存储在一个数组中,其值的范围为1到N。数组中的数字表示要达到开花状态的日期。因此,flower [i] = x。第x朵花将在第i天盛开。

开花条件是什么?

K是我们将要处理的数字。 我们将找到两朵花盛开的日子,两朵花之间有k朵不盛开的花。 这样就解开了K个空插槽背后的谜团,或者是吗?

图片代表一千个单词。 因此,我不会夸大其词,而是要通过一个示例进行输入。

输入:

花:[5,3,1,4,2]

k:1

输出2

在第二天,第三朵和第五朵花盛开,留下一朵仍在盛开的花。

图示相同的图像

K个空插槽
显示盛开的图案的插图

如何解决这个问题?

我将要描述的方法使用滑动窗口方法。 您可以在这个主题上遇到很多问题, 退房 在我们继续学习之前。

不用再拖延了,让我们直接进入K个空槽的解决方案

  • 让我们创建一个 排列 命名的日子,以保持该天盛开的花朵编号的位置
  • Days [flower [i] -1]将保持位置,即i + 1
  • 我们保持变量min来保存答案
  • 以上两个步骤可帮助我们继续使用滑动窗口,因此对我们而言很重要
    • 因此,我们从K空插槽的滑动窗口开始
    • 我们保持大小为k + 2的滑动窗口
    • 在任何时间点,如果left = i,则right = i + k + 1
    • 我们检查每个元素是否大于左右
      • 只要我们遵守这条规则,我们就会继续
      • 如果不是,那么我们考虑下一个窗口
  • 当我们到达窗口的末尾时,我们检查左元素和右元素的最大值
  • 然后将获得的值与我们在最小

上面说明的过程使我们逐步找到了一个完美的子阵列,该子阵列符合在盛开的花朵之间出现晚绽放的条件。

适用于K空插槽的Java代码

import java.util.*;
public class kslots
{
  public static int emoty(int[] blooms,int k)
  {
    int days[]=new int[blooms.length];
    for(int i=0;i<days.length;i++)
    {
      days[blooms[i]-1]=i+1;
    }
    int left  =0;
    int right =k+1;
    int min   =Integer.MAX_VALUE;
    for(int i=1;right<days.length;i++)
    {
      if(days[i]>days[left] && days[i]>days[right])
        continue;
      if(i==right)
        min=Math.min(min,Math.max(days[left],days[right]));
      left  =i;
      right =left+k+1;
    }
    if(min==Integer.MAX_VALUE)
      return -1;
    else
      return min;
  }
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int blooms[]=new int[n];
    for(int i=0;i<n;i++)
      blooms[i]=sc.nextInt();
    int k=sc.nextInt();
    int num=emoty(blooms,k);
    System.out.println(num);
  }
}

K空插槽的C ++代码

#include<iostream>
using namespace std;
int maxs(int a,int b)
{
  if(a>b)
    return a;
  else
    return b;
}
int mins(int a,int b)
{
  if(a>b)
    return b;
  else
    return a;
}
int emoty(int blooms[],int k)
{
  unsigned int m=(sizeof(blooms)/sizeof(blooms[0]));
  int days[m];
  for(int i=0;i<m;i++)
  {
    days[blooms[i]-1]=i+1;
  }
  int left  =0;
  int right =k+1;
  int min   =9999;
  for(int i=1;right<m;i++)
  {
    if(days[i]>days[left] && days[i]>days[right])
        continue;
    if(i==right)
      min=mins(min,maxs(days[left],days[right]));
    left=i;
    right=left+k+1;
  }
  if(min=9999)
    return -1;
  else
    return min;
}
int main()
{
  int n,k;
  cin>>n;
  int blooms[n];
  for(int i=0;i<n;i++)
    cin>>blooms[i];
  cin>>k;
  int num=emoty(blooms,k);
  cout<<num;
}
[5,3,1,4,2]
1
2

复杂度分析

算法的时间复杂度= O(n)

算法的空间复杂度= O(n)

对于K个空插槽,情况如何?

  • 遍历数组,我们选择滑动窗口,这是一个微不足道的操作
  • 在最坏的情况下,滑动窗口可能会逐个滑动通过每个元素
    • 这使得算法的运行时复杂度为O(n)
    • 不仅这个问题,而且此协议引起的任何其他问题都将涉及O(n)时间
  • 当我们创建整个数组的副本时,空间复杂度为O(n)

我希望这种解释 K个空插槽 很棒而且可以理解!

继续收看Tutorialcup😀

參考資料