K 빈 슬롯

난이도 하드
자주 묻는 질문 아마존 구글
배열 주문 된지도조회수 49
링크드 인버퍼레딧텀블러

K 빈 슬롯은 정원사의 딜레마를 올바르게 나타내며 우리의 조건에 맞는 꽃을 선택하려고합니다.

우리 정원사는 N 슬롯 필드가 있습니다. 정원사는 각 슬롯에 꽃을 심었습니다. 각각의 꽃은 특정에 피어 유일한 일. 또한 상록 꽃을 심었습니다. 꽃이 피면 고려 개화 영원히.

각각의 꽃이 피는 날은 1에서 N까지의 값 범위를 갖는 배열에 저장됩니다. 배열의 숫자는 개화 상태에 도달 할 날을 나타냅니다. 따라서 꽃 [i] = x. x 번째 꽃은 i 일에 피게됩니다.

개화 상태는 어떻습니까?

K는 우리가 처리 할 숫자입니다. 두 꽃이 그 사이에 k 개의 꽃이 피지 않는 꽃이 피는 날을 찾을 것입니다. K 빈 슬롯 뒤에 숨겨진 수수께끼가 풀리나요?

이미지는 천 단어를 말합니다. 따라서 과장하기보다는 입력을 위해 샘플을 살펴 보겠습니다.

입력:

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

k : 1

출력 : 2

둘째 날에는 세 번째와 다섯 번째 꽃이 피고 아직 꽃이 피고 있습니다.

같은 것을 보여주는 이미지

K 빈 슬롯핀
개화 패턴을 보여주는 일러스트

문제에 접근하는 방법?

제가 설명하려는 접근 방식은 슬라이딩 윈도우 접근 방식을 사용합니다. 이 주제에 대한 다양한 문제가 있습니다. 체크 아웃 자세히 알아보기 전에

더 이상 지체하지 않고 K Empty Slots의 솔루션으로 바로 이동하겠습니다.

  • 우리가 만들자 정렬 특정 날짜에 피는 꽃 번호의 위치를 ​​유지하기 위해 명명 된 날짜
  • Days [flower [i] -1]은 i + 1의 위치를 ​​유지합니다.
  • 답변을 유지하기 위해 가변 최소값을 유지합니다.
  • 위의 두 단계는 슬라이딩 윈도우를 진행하는 데 도움이되므로 진행하는 데 중요합니다.
    • 따라서 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을 계속 시청하세요 😀

참조

링크드 인버퍼레딧텀블러
Translate »