Kth مفقود رقم موجب حل Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في Facebook Microsoft
مجموعة تجزئة

بيان المشكلة

في المسألة "Kth Missing Positive Number" ، نحصل على مصفوفة arr ، مرتبة حسب زيادة صارمة طلب ورقم ك.

مهمتنا هي إيجاد العدد الناقص الموجب Kth في المصفوفة.

مثال

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

التفسير:

Kth مفقود رقم موجب حل Leetcode

كما هو الحال في المصفوفة المعطاة ، العدد الأول المفقود هو 5 والعدد الثاني المفقود هو 6. إذن ، الإجابة هي 6.

القوة الغاشمة أpproach لـ Kth مفقود رقم موجب حل Leetcode

نهج القوة الغاشمة لحل هذه المشكلة هو كما يلي:

  1. اجتياز المصفوفة.
  2. في كل مرة سنقوم بحساب عدد الأعداد الناقصة.
  3. إذا كان عدد الأعداد الموجبة المفقودة أكبر من أو يساوي k ، فسنقوم بإرجاع i + k.
  4. بعد اجتياز المصفوفة بالكامل إذا كان عدد العناصر المفقودة أقل من k ، فسنقوم بإرجاع حجم المصفوفة + k.

تطبيق

كود C ++ لـ Kth مفقود رقم موجب

#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

كود Java لـ Kth مفقود رقم موجب

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

تحليل التعقيد لـ Kth المفقود في حل Leetcode للأرقام الموجبة

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (ن) لأننا نستخدم بحثًا خطيًا يستغرق وقتًا (س) في أسوأ الحالات. هنا n هو طول المصفوفة المعطاة.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه يا (1) لأننا نستخدم متغيرًا فقط لتخزين الإجابة.

بحث ثنائي أpproach لـ Kth مفقود رقم موجب حل Leetcode

التعقيد الزمني للخوارزمية أعلاه هو O (n) لأننا قد نحتاج إلى اجتياز المصفوفة الكاملة في أسوأ الحالات. يمكننا تحسين التعقيد الزمني للحل باستخدام بحث ثنائي بدلاً من البحث الخطي.

  1. دعنا أولاً نحدد نطاق بحثنا عن البحث الثنائي. لذا ستكون البداية هي الفهرس 0 وستكون النهاية هي الفهرس الأخير للصفيف المحدد.
  2. سنجد المؤشر المتوسط ​​ثم سنتحقق مما إذا كان عدد الأرقام الموجبة المفقودة أقل من k:
    1. ثم ستصبح البداية منتصف + 1.
    2. آخر ستصبح منتصف.
  3. نهاية العودة + k.

تطبيق

كود C ++ لـ Kth مفقود رقم موجب

#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

كود Java لـ Kth مفقود رقم موجب

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

تحليل التعقيد لـ Kth المفقود في حل Leetcode للأرقام الموجبة

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (تسجيل ن) لأننا نستخدم بحثًا ثنائيًا يستغرق وقت O (تسجيل الدخول) في أسوأ الحالات. هنا n هو طول المصفوفة المعطاة.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه يا (1) لأننا نستخدم متغيرًا فقط لتخزين الإجابة.

المراجع