K خالی سلاٹ


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایمیزون گوگل
لڑی حکم دیا نقشہ

کے خالی سلاٹ ایک باغبان کی مشکوک کو صحیح طور پر پیش کرتے ہیں ، جو ہماری حالت کے مطابق پھول لینے کی کوشش کرتے ہیں۔

ہمارے مالی کے پاس N-سلاٹس کا ایک فیلڈ ہے۔ مسٹر باغبان نے ہر ایک سلاٹ میں ایک پھول لگایا ہے۔ ہر پھول ایک خاص پر کھل جائے گا منفرد دن نیز ، ہم نے سدا بہار پھول لگائے ہیں۔ ایک بار وہ کھل گئے ، وہ ہیں سمجھا کھلی ہمیشہ کے لئے.

جس دن ان میں سے ہر ایک پھول کھل رہا ہے اس دن میں ایک صف میں ذخیرہ کیا جاتا ہے جس کی اقدار 1 سے N تک ہوتی ہیں۔ سرنی میں نمبر اس دن کی نمائندگی کرتا ہے جس دن کھلتے ہوئے مقام کو حاصل کرنے جا رہے ہیں۔ لہذا ، اگر پھول [i] = x۔ اس دن x ویں پھول کھل جائے گا i۔

کھلنے والی حالت کیا ہے؟

K ایک ایسی تعداد ہے جس کا ہم خیال رکھیں گے۔ ہم وہ دن ڈھونڈیں گے جس دن دو پھول کھل رہے ہیں ان کے درمیان کے نہ کھلے ہوئے پھول اس طرح کے خالی سلاٹوں کے پیچھے بھید اس طرح کھلا ہے ، یا یہ ہے؟

امیجز ایک ہزار الفاظ کے لئے بولتی ہیں۔ لہذا ، مبالغہ آرائی کے بجائے ، میں ایک ان پٹ کے نمونے کے ذریعہ دوڑ رہا ہوں۔

ان پٹ:

پھول: [5,3,1,4,2،XNUMX،XNUMX،XNUMX،XNUMX]

k: 1

آؤٹ پٹ: 2

دوسرے دن ، تیسرا اور پانچواں پھول کھل گیا جس نے ایک پھول چھوڑا جو ابھی تک کھلتا ہے۔

ایک ہی مثال کے طور پر تصویر

K خالی سلاٹ
کھلتا ہوا نمونہ دکھا رہی ایک مثال

مسئلے سے کیسے رجوع کریں؟

میں جس نقطہ نظر کو بیان کرنے والا ہوں اس میں سلائیڈنگ ونڈو اپروچ کا استعمال ہوتا ہے۔ اس موضوع پر ہمارے پاس بہت ساری پریشانی ہے جو آپ کر سکتے ہیں چیک مزید جاننے کے لئے آگے بڑھنے سے پہلے

کسی مزید تاخیر کے بغیر آئیے ہم K کے خالی سلاٹوں کے حل میں سیدھے کود جائیں

  • آئیے ایک بنائیں صف اس مخصوص دن پر کھلنے والے پھولوں کی تعداد کو برقرار رکھنے کے لئے نامزد دن
  • دن [پھول [i] -1] پوزیشن پر رہیں گے یعنی i + 1
  • ہم جواب کو برقرار رکھنے کے لئے متغیر منٹ کو برقرار رکھتے ہیں
  • مذکورہ بالا دو مراحل سلائیڈنگ ونڈو کے ساتھ آگے بڑھنے میں ہماری مدد کرتے ہیں لہذا ہمارے لئے آگے بڑھنے کے لئے یہ ضروری ہے
    • ہم اس طرح کے خالی سلاٹوں کے لئے اپنی سلائیڈنگ ونڈو سے شروع کرتے ہیں
    • ہم سائز k + 2 کی سلائیڈنگ ونڈو کو برقرار رکھتے ہیں
    • کسی بھی وقت اگر بائیں = i پھر دائیں = i + k + 1
    • ہم ہر عنصر کی جانچ پڑتال کرتے ہیں اگر یہ بائیں اور دائیں سے زیادہ ہے
      • جب تک ہم اس اصول کی پابندی کر رہے ہیں ہم جاری رکھیں گے
      • اگر ہم نہیں ہیں تو ہم اگلی ونڈو پر غور کریں
  • جب ہم ونڈو کے اختتام تک پہنچ جاتے ہیں تو ہم زیادہ سے زیادہ بائیں اور دائیں عناصر کی جانچ کرتے ہیں
  • حاصل کردہ قیمت کا موازنہ اس موجودہ قیمت سے کیا جاتا ہے جو ہمارے پاس کم سے کم ہے

ہم جس عمل کے بارے میں اوپر بیان کر رہے ہیں وہ ہمیں کامل سبیارے کی کھوج میں لے رہا ہے جو کھلتے پھولوں کے درمیان دیر سے پھول آنے کی شرائط کی تعمیل کرتا ہے۔

K- خالی سلاٹوں کے لئے جاوا کوڈ

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);
  }
}

C ++ K- خالی سلاٹوں کے لئے کوڈ

#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 خالی سلاٹوں کے ل for یہ کیسا ہے؟

  • سرے سے جڑتے ہوئے ہم اپنی سلائیڈنگ ونڈوز کا انتخاب کرتے ہیں جو معمولی کارروائی ہے
  • خراب صورتحال میں سلائڈنگ ونڈو ایک ایک کرکے ہر عنصر میں پھسل سکتی ہے
    • اس سے الگورتھم O (n) کی رن ٹائم کی پیچیدگی ہوجاتی ہے
    • نہ صرف یہ مسئلہ ہے بلکہ کوئی اور مسئلہ جو اس پروٹوکول کے تحت ہوتا ہے اس میں O (n) کا وقت شامل ہوگا
  • خلائی پیچیدگی O (n) ہے کیونکہ ہم پوری صف کی ایک کاپی تیار کرتے ہیں

مجھے امید ہے کہ اس وضاحت کے لئے K خالی سلاٹ بہت اچھا اور قابل فہم تھا!

ٹیوٹوریلکپ tun میں جاری رکھیں

حوالہ جات