האלמנט הגדול ביותר ב- פתרונות Array Leetcode  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ Byte eBay Expedia פייסבוק Google לינקדין מיקרוסופט אורקל Salesforce Spotify מעבדות וולמארט
אלגוריתמים מערך קידוד הפרד ומשול ערימה ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions

בבעיה זו, עלינו להחזיר את האלמנט הגדול ביותר ב- k לא ממוינת מערך. שים לב שהמערך יכול להכיל כפילויות. אז עלינו למצוא את Kth האלמנט הגדול ביותר בסדר הממוין, לא האלמנט Kth הגדול ביותר.

דוגמה  

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

גישה (מערך מיון)  

גישה זו היא ישר קדימה. ממיין את כל המערך. ועכשיו אתה יכול לספר על כל האלמנט הגדול ביותר במערך. אבל, זה מספיק בשביל פשוט למצוא את Kth האלמנט הגדול ביותר. לכן אנו יכולים להגיע לגישה טובה יותר.

אַלגוֹרִיתְם

  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

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

ניתוח מורכבות של מציאת האלמנט הגדול ביותר ב- K במערך לא ממוין

מורכבות זמן

O (NlogN), כיוון שאנחנו צריכים למיין את המערך. N = גודל המערך

ראה גם
פתרון Leetcode חוצה שבילים

מורכבות חלל

O (1), כשאנחנו משתמשים במרחב קבוע. הערות: סוג() פונקציה יכולה להשתמש עַל) זיכרון. אבל זה לא תמיד המקרה.

גישה (בחירה מהירה)  

כפי שדנו בגישתנו הקודמת, עלינו רק למצוא את kth האלמנט הגדול ביותר במערך. באופן פשוט יותר, אנו זקוקים לאלמנט הקטן (n - k + 1) במערך. מדברים על מין אנחנו יכולים לחשוב סידור מהיר, שיש לו גישה דומה. במיקום מהיר, תוך בחירת a ציראנו מבטיחים שהוא יגיע לאינדקס הנכון במערך לאחר המחיצה.

מה אם, עשינו מחיצה דומה עד ל- (n - kהמדד מקבל את הערך הנכון שלו. זה מה שאנחנו הולכים לעשות בגישה זו:

האלמנט הגדול ביותר במערך לא ממוין של פתרונות Leetcode

בחר ציר אקראי כלשהו ומחלק את המערך סביבו. אם זה מגיע למדד שאנחנו רוצים (n - k). ואז, זהו האלמנט הגדול ביותר ב- Kth. אחרת, אנו יודעים שהמדד הנדרש נמצא משמאל לו או מימין לו. לאחר מכן נוכל להתקשר ל חֲלוּקָה() פונקציה במקביל מערך משנה כדי למצוא את המדד הנדרש, ולכן, את ערכו.

אבל, האם הגישה לעיל בהחלט טובה יותר מ- מיון אחד? אנו יודעים שהמקרה הגרוע ביותר של quicksort מתרחש כאשר אנו בוחרים את האלמנט הקטן / הגדול ביותר כציר שלנו כמו במקרה זה,

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

ובעיית המשנה כמעט זהה לבעיה וגורמת למורכבות הזמן O (N * N). באופן דומה, פונקציית המחיצה שלנו יכולה לבצע שיחות כאלה. על מנת לפתור זאת, אנו נדאג שנבחר בא אקראי ציר בכל נקודת חלוקה.

ראה גם
שאילתות ב- XOR של המחלק המוזר הגדול ביותר בטווח

אַלגוֹרִיתְם

  1. צור בחירה מהירה() פונקציה המחזירה את (N - K) th “הקטן ביותראלמנט
  2. צור חֲלוּקָה() פונקצית עוזר שתחזיר את האינדקס הנכון של כל אחד מהם באופן אקראי ציר שנבחר
  3. עכשיו, עד שנגיע לנקודה שבה חֲלוּקָה() מחזיר את האינדקס השווה ל 'KYou
    • התקשר למחיצה () על א אקראי ציר
    • אם אינדקס הציר שהוחזר זהה ל K
      • להחזיר את אלמנט הציר
    • אחרת אם מדד הציר שהוחזר נמוך מ- K
      • מחיצת שיחה () מופעלת תקין מערך משנה של מדד הציר
    • אחרת אם אינדקס הציר שהוחזר הוא יותר מ K
      • מחיצת שיחה () מופעלת מערך משנה שמאלי של מדד הציר
  4. עכשיו בחירה מהירה() החזיר את האינדקס (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

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

ניתוח מורכבות של מציאת האלמנט הגדול ביותר ב- K במערך לא ממוין

מורכבות זמן

ניתן לבטא את יחס ההישנות כ- (N = גודל המערך):

ראה גם
תיקיית יומן הסורקים פתרון Leetcode

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

מכיוון שאנו מצפים כי ציר שנבחר באופן אקראי חילק את המערך לשני חצאים. על סמך זה, ניתן לאמוד בערך את המורכבות כ- T (N) = 2N - logN = ~ O (N).

אז האלגוריתם הוא ליניארי. עם זאת, במקרה הגרוע ביותר, כאשר הצירים האקראיים שנבחרו הם כולם הגדולים / הקטנים ביותר במערך, מורכבות הזמן הופכת להיות O (N * N). אבל במערך גדול מאוד, סביר מאוד שזה יקרה.

מורכבות חלל

O (1), כמו שמשתמשים רק במרחב קבוע.