Kth காணாமல் போன நேர்மறை எண் லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது பேஸ்புக் மைக்ரோசாப்ட்
அணி ஹேஷிங்

பொருளடக்கம்

சிக்கல் அறிக்கை

“Kth Missing Positive Number” என்ற சிக்கலில் எங்களுக்கு வரிசை வரிசை வழங்கப்படுகிறது, இது வரிசைப்படுத்தப்படுகிறது கண்டிப்பாக அதிகரிக்கும் வரிசை மற்றும் ஒரு எண் k.

வரிசையில் Kth நேர்மறை காணாமல் போன எண்ணைக் கண்டுபிடிப்பதே எங்கள் பணி.

உதாரணமாக

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

விளக்கம்:

Kth காணாமல் போன நேர்மறை எண் லீட்கோட் தீர்வு

கொடுக்கப்பட்ட வரிசையைப் போலவே, காணாமல் போன முதல் எண் 5 மற்றும் இரண்டாவது காணாமல் போன எண் 6 ஆகும். எனவே, பதில் 6 ஆகும்.

முரட்டு படை A.Kth காணாமல் போன நேர்மறை எண் லீட்கோட் தீர்வுக்கான pproach

இந்த சிக்கலை தீர்க்க முரட்டுத்தனமான அணுகுமுறை பின்வருமாறு:

  1. வரிசையை கடந்து செல்லுங்கள்.
  2. ஒவ்வொரு முறையும் காணாமல் போன எண்களின் எண்ணிக்கையை கணக்கிடுவோம்.
  3. காணாமல் போன நேர்மறை எண்களின் எண்ணிக்கை k ஐ விட அதிகமாகவோ அல்லது சமமாகவோ இருந்தால், நான் i + k ஐ திருப்பித் தருகிறோம்.
  4. வரிசையின் முழுமையான பயணத்திற்குப் பிறகு, காணாமல் போன தனிமங்களின் எண்ணிக்கை k ஐ விடக் குறைவாக இருந்தால், நாம் வரிசை + k இன் அளவைத் தருவோம்.

நடைமுறைப்படுத்தல்

Kth காணாமல் போன நேர்மறை எண்ணிற்கான 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

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 காணாமல் போன நேர்மறை எண் லீட்கோட் தீர்வின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

மேலே உள்ள குறியீட்டின் நேர சிக்கலானது ஓ (n) ஏனென்றால் மிக மோசமான நிலையில் O (n) நேரத்தை எடுக்கும் நேரியல் தேடலைப் பயன்படுத்துகிறோம். இங்கே n என்பது கொடுக்கப்பட்ட வரிசையின் நீளம்.

விண்வெளி சிக்கலானது

மேலே உள்ள குறியீட்டின் இட சிக்கலானது ஓ (1) ஏனென்றால் பதிலைச் சேமிக்க ஒரு மாறி மட்டுமே பயன்படுத்துகிறோம்.

பைனரி தேடல் A.Kth காணாமல் போன நேர்மறை எண் லீட்கோட் தீர்வுக்கான pproach

மேலே உள்ள வழிமுறையின் நேர சிக்கலானது O (n) ஆகும், ஏனெனில் மோசமான நிலையில் முழுமையான வரிசையை நாம் பயணிக்க வேண்டியிருக்கும். நேரியல் தேடலுக்கு பதிலாக பைனரி தேடலைப் பயன்படுத்தி தீர்வின் நேர சிக்கலை மேம்படுத்தலாம்.

  1. பைனரி தேடலுக்கான எங்கள் தேடலின் வரம்பை முதலில் வரையறுப்போம். எனவே தொடக்கமானது குறியீட்டு 0 ஆகவும், முடிவு கொடுக்கப்பட்ட வரிசையின் கடைசி குறியீடாகவும் இருக்கும்.
  2. நடு குறியீட்டைக் கண்டுபிடிப்போம், பின்னர் காணாமல் போன நேர்மறை எண்களின் எண்ணிக்கை k ஐ விடக் குறைவாக இருக்கிறதா என்று சோதிப்போம்:
    1. தொடக்கமானது நடுப்பகுதியில் +1 ஆக மாறும்.
    2. மற்ற முடிவு நடுவாக மாறும்.
  3. திரும்ப முடிவு + கே.

நடைமுறைப்படுத்தல்

Kth காணாமல் போன நேர்மறை எண்ணிற்கான 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

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 காணாமல் போன நேர்மறை எண் லீட்கோட் தீர்வின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

மேலே உள்ள குறியீட்டின் நேர சிக்கலானது ஓ (பதிவு n) ஏனென்றால் மிக மோசமான நிலையில் O (logn) நேரத்தை எடுக்கும் பைனரி தேடலை நாங்கள் பயன்படுத்துகிறோம். இங்கே n என்பது கொடுக்கப்பட்ட வரிசையின் நீளம்.

விண்வெளி சிக்கலானது

மேலே உள்ள குறியீட்டின் இட சிக்கலானது ஓ (1) ஏனென்றால் பதிலைச் சேமிக்க ஒரு மாறி மட்டுமே பயன்படுத்துகிறோம்.

குறிப்புகள்