Kth ຂາດຕົວເລກບວກໃນການແກ້ໄຂ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ເຟສບຸກ Microsoft
Array ແຮກ

ບັນຫາບັນຫາ

ໃນບັນຫາ“ ເລກທີທີ່ຂາດໄປໃນທາງເລກທີ K” ພວກເຮົາໄດ້ຖືກຈັດເຂົ້າມາ, ເຊິ່ງຖືກຈັດຮຽງເຂົ້າ ເພີ່ມຂື້ນຢ່າງເຂັ້ມງວດ ຄໍາສັ່ງແລະຈໍານວນ k.

ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາຕົວເລກທີ່ຂາດໄປໃນທາງບວກຂອງ Kth ໃນຂບວນການ.

ຍົກຕົວຢ່າງ

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

ຄໍາອະທິບາຍ:

Kth ຂາດຕົວເລກບວກໃນການແກ້ໄຂ Leetcode

ຄືກັບໃນອາເລທີ່ລະບຸໄວ້, ຕົວເລກທີ່ຂາດຫາຍໄປຄັ້ງ ທຳ ອິດແມ່ນ 5 ແລະຕົວເລກທີ່ຂາດຫາຍໄປທີສອງແມ່ນ 6. ດັ່ງນັ້ນ, ຄຳ ຕອບແມ່ນ 6.

Brute Force Approach ສຳ ລັບ Kth ທີ່ຂາດຫາຍໄປໃນທາງບວກ Leetcode Solution

ວິທີການໃຊ້ ກຳ ລັງແຮງເພື່ອແກ້ໄຂບັນຫານີ້ມີດັ່ງນີ້:

  1. ຂ້າມອາເລ.
  2. ທຸກໆຄັ້ງພວກເຮົາຈະ ຄຳ ນວນເລກທີ່ຂາດໄປ.
  3. ຖ້າຫາກວ່າຕົວເລກຂອງຕົວເລກບວກທີ່ຂາດຫາຍໄປແມ່ນໃຫຍ່ກວ່າຫຼືເທົ່າກັບ k ພວກເຮົາກໍ່ຈະກັບຄືນ i + k.
  4. ຫຼັງຈາກເສັ້ນທາງທີ່ສົມບູນຂອງອາເລຖ້າ ຈຳ ນວນຂອງອົງປະກອບທີ່ຂາດຫາຍໄປ ໜ້ອຍ ກ່ວາ k ແລ້ວພວກເຮົາຈະສົ່ງຄືນຂະ ໜາດ ຂອງ array + 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) ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງໃຊ້ການຄົ້ນຫາແບບເສັ້ນທີ່ໃຊ້ເວລາ O (n) ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ. ນີ້ n ແມ່ນຄວາມຍາວຂອງອາເລທີ່ໃຫ້.

ຄວາມສັບສົນໃນອະວະກາດ

ຄວາມສັບສົນໃນພື້ນທີ່ຂອງລະຫັດຂ້າງເທິງແມ່ນ O (1) ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ຕົວແປເພື່ອເກັບ ຄຳ ຕອບ.

ການຄົ້ນຫາຖານສອງpproach ສຳ ລັບ Kth ທີ່ຂາດຫາຍໄປໃນທາງບວກ Leetcode Solution

ຄວາມສັບສົນທີ່ໃຊ້ເວລາຂອງສູດການຄິດໄລ່ຂ້າງເທິງນີ້ແມ່ນ O (n) ເພາະວ່າພວກເຮົາອາດຈະຕ້ອງການແກ້ໄຂອາເລທີ່ສົມບູນໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ. ພວກເຮົາສາມາດປັບປຸງຄວາມສັບສົນຂອງເວລາຂອງການແກ້ໄຂໂດຍໃຊ້ການຄົ້ນຫາຖານສອງໃນການຊອກຫາແບບເສັ້ນ.

  1. ທຳ ອິດໃຫ້ ກຳ ນົດຂອບເຂດຂອງການຄົ້ນຫາ ສຳ ລັບການຄົ້ນຫາຖານສອງ. ດັ່ງນັ້ນການເລີ່ມຕົ້ນຈະເປັນດັດຊະນີ 0 ແລະທ້າຍຈະເປັນດັດຊະນີສຸດທ້າຍຂອງອາເລທີ່ໃຫ້.
  2. ພວກເຮົາຈະຊອກຫາດັດສະນີກາງຫຼັງຈາກນັ້ນພວກເຮົາຈະກວດເບິ່ງວ່າ ຈຳ ນວນຕົວເລກໃນແງ່ບວກທີ່ຍັງຂາດແມ່ນ ໜ້ອຍ ກ່ວາ k:
    1. ຫຼັງຈາກນັ້ນເລີ່ມຕົ້ນຈະກາຍເປັນກາງ +1.
    2. ບ່ອນສຸດທ້າຍຈະກາຍເປັນກາງ.
  3. end end ກັບຄືນ + 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 (log n) ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ການຄົ້ນຫາຖານສອງທີ່ໃຊ້ເວລາ O (logn) ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ. ນີ້ n ແມ່ນຄວາມຍາວຂອງອາເລທີ່ໃຫ້.

ຄວາມສັບສົນໃນອະວະກາດ

ຄວາມສັບສົນໃນພື້ນທີ່ຂອງລະຫັດຂ້າງເທິງແມ່ນ O (1) ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ຕົວແປເພື່ອເກັບ ຄຳ ຕອບ.

ເອກະສານ