מצא מספרים K (או שכיחים ביותר) בזרם


רמת קושי בינוני
נשאל לעתים קרובות נאמן אמזון בעברית
מערך בליל

במציאת מספרים עליונים (או שכיחים ביותר) בבעיית זרם, נתנו מספר שלם מערך המורכב מכמה מספרים. הצהרת הבעיה אומרת שעליך לקחת אלמנט מהמערך, ואתה יכול לכלול רק מספרים k בראשם. עלינו להדפיס אלמנטים k עליונים שממוינים פחות ויותר בהתאם לתדירות שלהם.

דוגמה

קֶלֶט

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

תְפוּקָה

3, 1, 3, 1, 3, 4, 1, 3, 4, 6, 1, 3, 4, 6

הסבר למספרים k העליונים (או הנפוצים ביותר) בזרם

  • כשאנחנו קוראים את ה -1st אלמנט המערך שהוא 3 ועד עכשיו זה האלמנט היחיד עם תדר 1 שאנחנו מדפיסים '3'.
  • כשאנחנו קוראים את האלמנט השני של המערך שהוא 2 ויש לנו 1 ו -3 עם אותו תדר כלומר, 1 אבל 1 קטן מ -1 אז אנחנו מדפיסים 3 1.
  • בשלב הבא, כאשר אנו קוראים את האלמנט השלישי של המערך שהוא 3 ויש לנו 4, 3 ו -1 עם אותו תדר כלומר, 4 אך הסדר הממוין צריך להיות 1 1 3.
  • כשאנחנו קוראים את האלמנט הרביעי של המערך שהוא 4 ויש לנו 6, 3, 1 ו- 4 באותה תדר כלומר, 6 אבל הסדר הממוין צריך להיות 1 1 3 4.
  • כשאנחנו קוראים את האלמנט החמישי של המערך שהוא 5 ויש לנו 1, 3, 1 ו -4 כולם עם אותו תדר, כלומר, אך ל- 6 יש תדר גדול מ- 1 ולכן אלמנט שיש לו תדר גדול יותר צריך לבוא קודם לכן, לפי סדר מיון צריך להיות 1 1 1 3.

מצא מספרים K (או שכיחים ביותר) בזרם

קֶלֶט

[1, 2, 2, 4, 5] k = 4

תְפוּקָה

1, 1, 2, 2, 1, 2, 1, 4, 2, 1, 4, 5

הסבר למספר k העליון (או הנפוץ ביותר) בזרם

  • כשאנחנו קוראים את ה -1st אלמנט המערך שהוא 1 ועד עכשיו זה האלמנט היחיד עם תדר 1 שאנחנו מדפיסים '1'.
  • כשאנחנו קוראים את האלמנט השני של המערך שהוא 2 ויש לנו 2 ו -2 עם אותו תדר כלומר, 1 אבל 1 קטן מ -1 אז אנחנו מדפיסים 2 1.
  • בשלב הבא אנו קוראים את האלמנט השלישי של המערך שהוא 3 ויש לנו 2 תדר גדול מזה ולכן אנו מדפיסים 2 2 שכן אלמנט בעל תדר גבוה יותר מגיע קודם.
  • כשאנחנו קוראים את האלמנט הרביעי של המערך שהוא 4 ויש לנו 4 ו -4 עם תדר 1, אז אנחנו מדפיסים 1 2 1.
  • כשאנחנו קוראים את האלמנט החמישי של המערך שהוא 5 ויש לנו 5, 1 ו- 4 כולם עם אותו תדר, כלומר, אבל ל- 5 יש תדר גדול מ- 1 ולכן אלמנט שיש לו תדר גדול יותר צריך לבוא קודם לכן, סדר מסודר צריך להיות 2 1 2 1.

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

  1. הכריז על HashMap.
  2. הכריז על מערך.
  3. ספרו ואחסנו את התדרים של כל אלמנט במפה.
  4. הכנס את האלמנט למצב k + 1.
  5. חפש את האלמנט העליון וקבל את המיקום.
  6. חזרו מהעמדה שהתקבלה ל -0.
  7. החלף אם האלמנט בתדר גבוה יותר מאוחסן ליד ה- i.
  8. החלף אם התדר זהה אך האלמנט הבא גדול יותר.
  9. הדפס את k העליון עבור כל איטרציה של מערך.

הסבר ל מצא מספרים עליונים (או שכיחים ביותר) בזרם

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

נניח ששכללנו את האלמנט הראשון שהכנסנו למפה הזו בתדירות ואז העתק את אלמנט המערך הזה למערך זמני של מיקום kth. לאחר מכן אנו מבררים את מיקומו של אותו אלמנט במערך זמני ואוחסנים אותו למשתנה זמני כלשהו ומקטינים את המשתנה הטמפ 'בספירה 1.

בוטל ב תוך לולאה מאותה עמדה (משתנה זמני) ל -0 וקבעו בה שלושה תנאים. אם תדירות הערך של מיקום זה נמוכה מתדר האלמנט הבא, החלף את שני האלמנטים. אם התדר נמצא דומה אך האלמנט הבא גדול יותר מאשר להחליף אותו בהתאם. אחרת אנחנו צריכים לשבור את הלולאה.

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

לאחר החלפה וסידור של כל זוג אלמנטים עליונים k עלינו להדפיס מספרים עליונים (או הנפוצים ביותר) בזרם.

יישום למציאת מספרים K עליונים (או שכיחים ביותר) בזרם

תוכנית C ++

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

void kTop(int arr[], int n, int k)
{
  vector<int> topArray(k + 1);

  unordered_map<int, int> freq;

  for (int l = 0; l < n; l++)
    {
    freq[arr[l]]++;

    topArray[k] = arr[l];
    auto itr = find(topArray.begin(), topArray.end() - 1, arr[l]);

    for (int i = distance(topArray.begin(), itr) - 1; i >= 0; --i)
        {

      if (freq[topArray[i]] < freq[topArray[i + 1]])
        swap(topArray[i], topArray[i + 1]);

      else if ((freq[topArray[i]] == freq[topArray[i + 1]])
          && (topArray[i] > topArray[i + 1]))
        swap(topArray[i], topArray[i + 1]);
      else
        break;
    }
    for (int i = 0; i < k && topArray[i] != 0; ++i)
      cout << topArray[i] << ' ';
  }
  cout << endl;
}
int main()
{
  int k = 4;
  int arr[] = { 5, 2, 1, 3, 2 };
  int n = sizeof(arr) / sizeof(arr[0]);
  kTop(arr, n, k);
  return 0;
}
5 2 5 1 2 5 1 2 3 5 2 1 3 5

תוכנית Java

import java.io.*;
import java.util.*;
class topKElements
{
    public static int findTop(int[] arr, int ele)
    {
        for (int i = 0; i < arr.length; i++)
            if (arr[i] == ele)
                return i;
        return -1;
    }
    public static void printTopElements(int[] a, int n, int k)
    {
        int[] topArray = new int[k + 1];

        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < k + 1; i++)
            freq.put(i, 0);

        for (int l = 0; l < n; l++)
        {
            if (freq.containsKey(a[l]))
                freq.put(a[l], freq.get(a[l]) + 1);
            else
                freq.put(a[l], 1);

            topArray[k] = a[l];

            int i = findTop(topArray, a[l]);

            i -= 1;

            while (i >= 0)
            {
                if (freq.get(topArray[i]) < freq.get(topArray[i + 1]))
                {
                    int temp = topArray[i];
                    topArray[i] = topArray[i + 1];
                    topArray[i + 1] = temp;
                }
                else if ((freq.get(topArray[i]) == freq.get(topArray[i + 1])) && (topArray[i] > topArray[i + 1]))
                {
                    int temp = topArray[i];
                    topArray[i] = topArray[i + 1];
                    topArray[i + 1] = temp;
                }
                else
                {
                    break;
                }
                i -= 1;
            }
            for (int j = 0; j < k && topArray[j] != 0; j++)
            {
                System.out.print(topArray[j]+" ");
            }
        }
        System.out.println();
    }
    public static void main(String args[])
    {
        int k = 4;
        int[] arr = { 5, 2, 1, 3, 2 };
        int n = arr.length;
        printTopElements(arr, n, k);
    }
}
5 2 5 1 2 5 1 2 3 5 2 1 3 5

ניתוח מורכבות למציאת מספרים k עליונים (או שכיחים ביותר) בזרם

מורכבות זמן

O (n * k)  מכיוון שבכל חצייה מערך הטמפ 'בגודל "K" עוברת דרך "N" עוברת דרך.

מורכבות בחלל

O (n) מאחר ואחסון האלמנטים ב- HashMap לוקח "N" הזמן.

הפניות