ອົງປະກອບໃຫຍ່ທີສຸດໃນ Array Leetcode Solutions


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ ByteDance eBay Expedia ເຟສບຸກ ກູໂກ LinkedIn Microsoft Oracle Salesforce Spotify Walmart Labs
Array ແບ່ງແລະເອົາຊະນະ ຂີ້ເຫຍື້ອ

ໃນປັນຫາດັ່ງກ່າວນີ້, ພວກເຮົາຕ້ອງສົ່ງຄືນສິ່ງທີ່ໃຫຍ່ທີ່ສຸດຂອງ kth ໃນ an ບໍ່ຖືກຈັດ array. ໃຫ້ສັງເກດວ່າອາເລສາມາດເຮັດຊ້ ຳ ກັນໄດ້. ດັ່ງນັ້ນ, ພວກເຮົາຕ້ອງຊອກຫາສິ່ງທີ່ ກທ ອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດໃນການຈັດຮຽງ ລຳ ດັບ, ບໍ່ແມ່ນສ່ວນປະກອບທີ່ໃຫຍ່ທີ່ສຸດຂອງ Kth.

ຍົກຕົວຢ່າງ

A = {4 , 2 , 5 , 3 , 1}
K = 2
4
A = {7 , 2 , 6 , 4 , 3 , 5}
K = 4
4

ວິທີການ (ຈັດຮຽງແຖວ)

ວິທີການນີ້ແມ່ນກົງໄປກົງມາ. ຮຽງແຖວທັງ ໝົດ. ແລະຕອນນີ້ທ່ານສາມາດບອກອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດໃດໆໃນແຖວ. ແຕ່, ມັນພຽງພໍພຽງພໍ ສຳ ລັບພວກເຮົາທີ່ຈະຊອກຫາພຣະ ຄຳ ພີມໍມອນ ກທ ອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດ. ນັ້ນແມ່ນເຫດຜົນທີ່ພວກເຮົາສາມາດມາພ້ອມກັບວິທີການທີ່ດີກວ່າ.

ລະບົບວິເຄາະ

  1. ຮຽງແຖວ
  2. ເຂົ້າເຖິງອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດ Kth ຈາກດ້ານຫຼັງຂອງແຖວ
  3. ພິມ ຄຳ ຕອບ

ການປະຕິບັດຂອງສູດການຄິດໄລ່ເພື່ອຊອກຫາອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດ Kth ໃນຂບວນທີ່ບໍ່ຖືກຈັດລຽງ

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;



int KthLargest(vector <int> &a , int &k)
{
    int n = a.size();
    //kth largest = element on (n - k) index
    sort(a.begin() , a.end());
    return a[n - k];
}

int main()
{
    vector <int> a = {4 , 2 , 5 , 3 , 1};
    int k = 2;
    cout << KthLargest(a , k) << '\n';
}

Java Program

import java.util.Arrays;


class Kth_largest
{
    public static int KthLargest(int[] a, int k)
    {
        int n = a.length;
        Arrays.sort(a);
        return a[n - k];
    }

    public static void main(String args[])
    {
        int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
        System.out.println(KthLargest(a , k));
    }
}
4

ການວິເຄາະຄວາມສັບສົນຂອງການຊອກຫາອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດ Kth ໃນວົງຈອນທີ່ບໍ່ຖືກຈັດລຽງ

ຄວາມສັບສົນເວລາ

O (NlogN), ດັ່ງທີ່ພວກເຮົາຕ້ອງການຈັດຮຽງແຖວ. N = ຂະ ໜາດ ຂອງຂບວນ

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

ໂອ (1), ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່. ຫມາຍ​ເຫດ​: ຄັດ () ຫນ້າທີ່ສາມາດນໍາໃຊ້ ໂອ (N) ຄວາມຊົງ ຈຳ. ແຕ່ນັ້ນບໍ່ແມ່ນສະເຫມີໄປ.

ວິທີການ (ເລືອກດ່ວນ)

ດັ່ງທີ່ພວກເຮົາໄດ້ສົນທະນາໃນວິທີການທີ່ຜ່ານມາຂອງພວກເຮົາ, ພວກເຮົາພຽງແຕ່ຕ້ອງການຊອກຫາ kth ອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດໃນຂບວນການ. ໃນວິທີທີ່ລຽບງ່າຍ, ພວກເຮົາຕ້ອງການອົງປະກອບນ້ອຍທີ່ສຸດ (n - k + 1) ໃນແຖວ. ເວົ້າເຖິງການຈັດຮຽງ, ພວກເຮົາສາມາດຄິດເຖິງ quicksort, ເຊິ່ງມີວິທີການທີ່ຄ້າຍຄືກັນ. ໃນ quicksort, ໃນຂະນະທີ່ເລືອກ a pivot, ພວກເຮົາຮັບປະກັນວ່າມັນເຂົ້າເຖິງດັດສະນີທີ່ຖືກຕ້ອງຂອງມັນຢູ່ໃນຂບວນຫຼັງຈາກການແບ່ງປັນ.

ຈະເປັນແນວໃດຖ້າ, ພວກເຮົາໄດ້ເຮັດການແບ່ງປັນທີ່ຄ້າຍຄືກັນຈົນກ່ວາ (n - ກ) ດັດຊະນີນີ້ໄດ້ຮັບມູນຄ່າທີ່ຖືກຕ້ອງ. ນີ້ແມ່ນສິ່ງທີ່ພວກເຮົາຈະເຮັດໃນວິທີການນີ້:

ອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດໃນຕົວເລກທີ່ບໍ່ຖືກຈັດລຽງເປັນ Leetcode Solutions

ເລືອກເອົາຕົວ pivot ແບບສຸ່ມແລະແບ່ງປັນອາເລທີ່ຢູ່ອ້ອມຮອບມັນ. ຖ້າມັນເຂົ້າເຖິງດັດສະນີທີ່ພວກເຮົາປາດຖະ ໜາ (n - k). ຈາກນັ້ນ, ນີ້ແມ່ນອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດຂອງ Kth. ຖ້າບໍ່ດັ່ງນັ້ນ, ພວກເຮົາຮູ້ວ່າດັດສະນີທີ່ຕ້ອງການແມ່ນຢູ່ເບື້ອງຊ້າຍຂອງມັນຫລືຢູ່ເບື້ອງຂວາຂອງມັນ. ຈາກນັ້ນພວກເຮົາສາມາດໂທຫາ ການແບ່ງປັນ () ເຮັດວຽກໃນທີ່ສອດຄ້ອງກັນ ໃຕ້ດິນ ເພື່ອຊອກຫາດັດສະນີທີ່ຕ້ອງການ, ແລະດັ່ງນັ້ນ, ມູນຄ່າຂອງມັນ.

ແຕ່, ແມ່ນວິທີການຂ້າງເທິງນີ້ແນ່ນອນດີກ່ວາ ການຄັດເລືອກ ຫນຶ່ງ? ພວກເຮົາຮູ້ວ່າກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດຂອງ quicksort ເກີດຂື້ນເມື່ອພວກເຮົາເລືອກເອົາອົງປະກອບນ້ອຍທີ່ສຸດ / ໃຫຍ່ທີ່ສຸດເປັນຕົວຊີ້ວັດຂອງພວກເຮົາຄືກັນກັບໃນກໍລະນີດັ່ງກ່າວ,

T (N) = T (N - 1) + O (1)

ແລະຮູບແບບຍ່ອຍແມ່ນເກືອບຄືກັນກັບບັນຫາ, ເຮັດໃຫ້ເວລາ O (N * N) ສັບສົນ. ເຊັ່ນດຽວກັນ, ຟັງຊັນການແບ່ງປັນຂອງພວກເຮົາສາມາດໂທອອກໄດ້. ເພື່ອແກ້ໄຂບັນຫານີ້, ພວກເຮົາຈະຮັບປະກັນວ່າພວກເຮົາເລືອກ a random pivot ໃນທຸກໆຈຸດຂອງການແບ່ງປັນ.

ລະບົບວິເຄາະ

  1. ສ້າງເປັນ quickSelect () ໜ້າ ທີ່ທີ່ຈະກັບຄືນມາ (N - K) ທີ“ນ້ອຍທີ່ສຸດອົງປະກອບ
  2. ສ້າງເປັນ ການແບ່ງປັນ () helper function ເຊິ່ງຈະກັບມາດັດຊະນີທີ່ຖືກຕ້ອງຂອງໃດໆ randomly pivot ທີ່ເລືອກ
  3. ດຽວນີ້, ຈົນພວກເຮົາໄປຮອດຈຸດທີ່ ການແບ່ງປັນ () ເອົາດັດຊະນີເທົ່າກັບ 'K':
    • call partition () ໃສ່ a random pivot
    • ຖ້າດັດສະນີ pivot ກັບມາແມ່ນຄືກັນກັບ K
      • ສົ່ງຄືນສ່ວນປະກອບທີ່ເປັນ pivot
    • ອື່ນຖ້າດັດຊະນີ pivot ກັບມາແມ່ນ ໜ້ອຍ ກ່ວາ K
      • call partition () ສຸດ ສິດ ໃຕ້ດິນ ຂອງດັດຊະນີ pivot
    • ອື່ນຖ້າດັດຊະນີ pivot ກັບຄືນແມ່ນຫຼາຍກ່ວາ K
      • call partition () ສຸດ subarray ຊ້າຍ ຂອງດັດຊະນີ pivot
  4. ໃນປັດຈຸບັນທີ່ quickSelect () ໄດ້ກັບຄືນມາດັດຊະນີ (N - K), ພິມຜົນ

ການປະຕິບັດຂອງສູດການຄິດໄລ່ເພື່ອຊອກຫາອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດ Kth ໃນຂບວນທີ່ບໍ່ຖືກຈັດລຽງ

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;



int partition(int &l , int &r , vector <int> &a)
{
    int rnd = (rand() % (r - l + 1)) + l;
    swap(a[rnd] , a[r]);

    int idx = l;
    for(int i = l ; i < r ; i++)
    {
        if(a[i] < a[r])
        {
            swap(a[i] , a[idx]);
            idx++;
        }
    }

    swap(a[idx] , a[r]);
    return idx;
}

int quickSelect(int l , int r , int k , vector <int> &a)
{
    while(l <= r)
    {
        int pivotIdx = partition(l , r , a);
        if(pivotIdx == k)
            return a[pivotIdx];
        if(pivotIdx < k)
            l = pivotIdx + 1;
        else
            r = pivotIdx - 1;
    }
    return -1;
}


int KthLargest(vector <int> &a , int &k)
{
    int n = a.size();
    //kth largest = element on (n - k) index
    return quickSelect(0 , n - 1 , n - k , a);
}

int main()
{
    vector <int> a = {4 , 2 , 5 , 3 , 1};
    int k = 2;
    cout << KthLargest(a , k) << '\n';
}

Java Program

import java.util.Random;


class Kth_largest
{
    static void swap(int x , int y , int [] a)
    {
        int temp = a[y];
        a[y] = a[x];
        a[x] = temp;
        return;
    }

    static int partition(int l , int r , int [] a)
    {
        Random rndObject = new Random();
        int rnd = rndObject.nextInt(r - l + 1) + l , idx = l;
        swap(rnd , r , a);
        for(int i = l ; i < r ; i++)
        {
            if(a[i] < a[r])
            {
                swap(i , idx , a);
                idx++;
            }
        }
        swap(idx , r , a);
        return idx;
    }


    static int quickSelect(int l , int r , int k , int [] a)
    {
        while(l <= r)
        {
            int pivotIdx = partition(l , r , a);
            if(pivotIdx == k)
                return a[pivotIdx];
            if(pivotIdx < k)
                l = pivotIdx + 1;
            else
                r = pivotIdx - 1;
        }
        return -1;
    }

    public static int KthLargest(int[] a, int k)
    {
        int n = a.length;
        return quickSelect(0 , n - 1 , n - k , a);
    }


    public static void main(String args[])
    {
        int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
        System.out.println(KthLargest(a , k));
    }
}
4

ການວິເຄາະຄວາມສັບສົນຂອງການຊອກຫາອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດ Kth ໃນວົງຈອນທີ່ບໍ່ຖືກຈັດລຽງ

ຄວາມສັບສົນເວລາ

ຄວາມ ສຳ ພັນກັບການເກີດຂື້ນ ໃໝ່ ສາມາດສະແດງອອກເປັນ (N = ຂະ ໜາດ ຂອງຂບວນ):

T (N) = T (N / 2) + O (N - 1)

ເນື່ອງຈາກວ່າພວກເຮົາຄາດຫວັງວ່າຕົວ pivot ທີ່ຖືກເລືອກແບບສຸ່ມແບ່ງແຍກອາເລນເປັນສອງສ່ວນ. ອີງໃສ່ມັນ, ຄວາມສັບສົນສາມາດຖືກຄາດຄະເນປະມານ T (N) = 2N-logN = ~ O (N).

ດັ່ງນັ້ນ, ສູດການຄິດໄລ່ແມ່ນເປັນເສັ້ນ. ເຖິງຢ່າງໃດກໍ່ຕາມ, ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ, ເມື່ອຕົວເລືອກແບບສຸ່ມທີ່ຖືກຄັດເລືອກແມ່ນໃຫຍ່ທີ່ສຸດ / ນ້ອຍທີ່ສຸດໃນແຖວ, Time Complexity ກາຍເປັນ O (N * N). ແຕ່ໃນອາເລທີ່ມີຂະ ໜາດ ໃຫຍ່, ມັນອາດຈະເກີດຂື້ນ ໜ້ອຍ ທີ່ສຸດ.

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

ໂອ (1), ເປັນພຽງແຕ່ພື້ນທີ່ຄົງທີ່ເທົ່ານັ້ນທີ່ຖືກ ນຳ ໃຊ້.