Kth අස්ථානගත ධනාත්මක අංක ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ෆේස්බුක් මයික්රොසොෆ්ට්
අරා හැෂිං

ගැටළු ප්රකාශය

“Kth අස්ථානගත ධනාත්මක අංකය” යන ගැටලුවේදී අපට අරාව ලබා දී ඇත දැඩි ලෙස වැඩි වීම ඇණවුම සහ අංක k.

අපගේ කර්තව්‍යය වන්නේ අරාවෙහි ඇති Kth ධනාත්මක අස්ථානගත වූ අංකය සොයා ගැනීමයි.

උදාහරණයක්

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

පැහැදිලි කිරීම:

Kth අස්ථානගත ධනාත්මක අංක ලීට්කෝඩ් විසඳුම

දී ඇති අරාවෙහි මෙන්, පළමු අස්ථානගත වූ අංකය 5 වන අතර දෙවන අස්ථානගත වූ අංකය 6 වේ.

තිරිසන් බලය ඒ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) මක් නිසාද යත්, අප භාවිතා කරන්නේ රේඛීය සෙවුමකි. මෙහි n යනු දී ඇති අරාවේ දිග වේ.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ ඕ (1) මොකද අපි උත්තරය ගබඩා කරන්න විචල්‍යයක් විතරයි පාවිච්චි කරන්නේ.

ද්විමය සෙවීම A.Kth අස්ථානගත ධනාත්මක අංක ලීට්කෝඩ් විසඳුම සඳහා pproach

ඉහත ඇල්ගොරිතමයේ කාල සංකීර්ණතාව O (n) වන්නේ නරකම අවස්ථාවෙහිදී අපට සම්පූර්ණ අරාව හරහා ගමන් කිරීමට අවශ්‍ය විය හැකි බැවිනි. රේඛීය සෙවීම වෙනුවට ද්විමය සෙවුමක් භාවිතා කරමින් විසඳුමේ කාල සංකීර්ණතාව අපට වැඩි දියුණු කළ හැකිය.

  1. ද්විමය සෙවීම සඳහා අපගේ සෙවීමේ පරාසය පළමුව නිර්වචනය කරමු. එබැවින් ආරම්භය දර්ශකය 0 වන අතර අවසානය දී ඇති අරාවේ අවසාන දර්ශකය වේ.
  2. අපි මධ්‍ය දර්ශකය සොයා ගනිමු, නැතිවූ ධනාත්මක සංඛ්‍යා k ට වඩා අඩු දැයි අපි පරීක්ෂා කරමු:
    1. ආරම්භය මැද + 1 බවට පත්වේ.
    2. නැතිනම් අවසානය මැද බවට පත්වේ.
  3. ආපසු අවසානය + k.

ක්රියාත්මක කිරීම

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 අස්ථානගත ධනාත්මක අංක ලීට්කෝඩ් විසඳුමේ සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඉහත කේතයේ කාල සංකීර්ණතාව වේ ඕ (ලොග් එන්) මොකද අපි ද්විමය සෙවුමක් භාවිතා කරන්නේ නරකම අවස්ථාවක O (ලොග්) කාලය ගත වන බැවිනි. මෙහි n යනු දී ඇති අරාවේ දිග වේ.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ ඕ (1) මොකද අපි උත්තරය ගබඩා කරන්න විචල්‍යයක් විතරයි පාවිච්චි කරන්නේ.

ආශ්රිත