مثبت نمبر لیٹکوڈ حل سے Kth لاپتہ


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے فیس بک مائیکروسافٹ
لڑی ہیکنگ

مسئلہ یہ بیان

مسئلے میں “Kth لاپتہ مثبت نمبر” ہمیں ایک سرنی آرر دیا جاتا ہے ، جس میں ترتیب دیا گیا ہے سختی سے اضافہ آرڈر اور ایک نمبر k

ہمارا کام صف میں Kth مثبت لاپتہ نمبر تلاش کرنا ہے۔

مثال کے طور پر

arr = [1,2,3,4], k = 2
6

وضاحت:

مثبت نمبر لیٹکوڈ حل سے Kth لاپتہ

جیسا کہ دیئے گئے صفوں میں ، پہلا گمشدہ نمبر 5 اور دوسرا لاپتہ نمبر 6 ہے۔ لہذا ، جواب 6 ہے۔

بروٹ فورس اےpproach for Kth لاپتہ مثبت نمبر لیٹکوڈ حل

اس مسئلے کو حل کرنے کے لئے بروٹ فورس نقطہ نظر اس طرح ہے:

  1. صف کو عبور کریں۔
  2. جب بھی ہم لاپتہ نمبروں کی تعداد کا حساب لگائیں گے۔
  3. اگر گمشدہ مثبت تعداد کی تعداد k سے زیادہ یا مساوی ہے تو ہم i + k واپس کردیں گے۔
  4. صف کی مکمل ٹریورسال کے بعد اگر گمشدہ عناصر کی تعداد k سے کم ہے تو ہم صف + K کی شکل واپس کردیں گے۔

عمل

مثبت تعداد میں کیتھ کے گم ہونے کے لئے C ++ کوڈ

#include <bits/stdc++.h> 
using namespace std; 
    int findKthPositive(vector<int>& arr, int k) {
        for(int i=0;i<arr.size();i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.size()+k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

مثبت نمبر کے لئے کیتھ لاپتہ کیلئے جاوا کوڈ

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] arr, int k) {
        for(int i=0;i<arr.length;i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.length+k;
    }   
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

مثبت نمبر لیٹکوڈ حل غائب ہونے کا کیتھتھ کا پیچیدہ تجزیہ

وقت کی پیچیدگی

مذکورہ کوڈ کی ٹائم پیچیدگی ہے اے (ن) کیونکہ ہم ایک لکیری تلاش استعمال کر رہے ہیں جس میں او (n) وقت لگتا ہے۔ یہاں n دیئے گئے صف کی لمبائی ہے۔

خلائی پیچیدگی

مذکورہ کوڈ کی جگہ کی پیچیدگی ہے O (1) کیونکہ ہم جواب کو ذخیرہ کرنے کے لئے صرف متغیر کا استعمال کررہے ہیں۔

ثنائی تلاش اےpproach for Kth لاپتہ مثبت نمبر لیٹکوڈ حل

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

  1. آئیے پہلے بائنری تلاش کے ل our اپنی تلاش کی حد کی وضاحت کریں۔ تو آغاز انڈیکس 0 ہوگا اور اختتام دیئے گئے صفوں کا آخری انڈیکس ہوگا۔
  2. ہمیں وسط انڈیکس مل جائے گا پھر ہم جانچیں گے کہ گمشدہ مثبت تعداد کی تعداد k سے کم ہے:
    1. پھر شروعات کا وسط +1 ہو جائے گا۔
    2. ورنہ وسط ہو جائے گا.
  3. واپسی اختتام + k.

عمل

مثبت تعداد میں کیتھ کے گم ہونے کے لئے C ++ کوڈ

#include <bits/stdc++.h> 
using namespace std; 
int findKthPositive(vector<int>& A, int k) {
        int l = 0, r = A.size(), m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

مثبت نمبر کے لئے کیتھ لاپتہ کیلئے جاوا کوڈ

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] A, int k) {
        int l = 0, r = A.length, m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }  
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

مثبت نمبر لیٹکوڈ حل غائب ہونے کا کیتھتھ کا پیچیدہ تجزیہ

وقت کی پیچیدگی

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

خلائی پیچیدگی

مذکورہ کوڈ کی جگہ کی پیچیدگی ہے O (1) کیونکہ ہم جواب کو ذخیرہ کرنے کے لئے صرف متغیر کا استعمال کررہے ہیں۔

حوالہ جات