განსხვავება მასივის უმაღლეს და მინიმალურ სიხშირეებს შორის


Რთული ტური Easy
ხშირად ეკითხებიან ციხედ Fab Fourkites რობლოქსი Tesla
Array Hash დახარისხება

პრობლემა ”განსხვავება მასივში ყველაზე მაღალ და მინიმალურ სიხშირეებს შორის” აცხადებს, რომ თქვენ გაქვთ მთელი რიცხვი მასივი. პრობლემის დებულება ითხოვს მაქსიმალური განსხვავების გარკვევას მასივში ორი განსხვავებული რიცხვის უმაღლეს და ყველაზე დაბალ სიხშირეს შორის.

მაგალითი

განსხვავება მასივის უმაღლეს და მინიმალურ სიხშირეებს შორის

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

განმარტება

სიხშირე 1 → 3 (უმაღლესი სიხშირე)

5 → 1 სიხშირე (ყველაზე დაბალი სიხშირე)

arr[] = {5, 4, 5, 5, 5, 3, 4 }
3

განმარტება

სიხშირე 5 → 4 (უმაღლესი სიხშირე)

3 → 1 სიხშირე (ყველაზე დაბალი სიხშირე)

ალგორითმი

  1. გამოაცხადეთ ა რუკა.
  2. შეინახეთ და დაითვალეთ მასივის ელემენტის სიხშირე.
  3. უცნობია მაქსიფრეკი 0-მდე და მინფრეკი to n.
  4. გაიარეთ რუკაზე:
    1. შეიტყვეთ მაქსიმალური მნიშვნელობა maxfreq- სა და სიხშირეს შორის რუკაზე და შეინახეთ maxfreq- ში.
    2. გაეცანით მინიფრეკს და სიხშირეს მინიმალური მნიშვნელობა რუკაზე და შეინახეთ იგი minfreq- ში.
  5. დაბრუნება (maxfreq-minfreq).

განმარტება

ჩვენ გვაქვს მთელი რიგი მთელი რიცხვებისა. ჩვენი ამოცანაა გაირკვეს მაქსიმალური განსხვავება მასივში არსებული ორი განსხვავებული რიცხვის ყველაზე მაღალ და ყველაზე დაბალ შემთხვევას შორის. ჩვენ ვაპირებთ გამოვიყენოთ ჰასინგი. ჰეშინგი გთავაზობთ ამ საკითხის გადაჭრის ეფექტურ გზას. ჩვენ ვაპირებთ განვაცხადოთ რუქა და დავათვალოთ თითოეული მასივის ელემენტის სიხშირეები და ერთდროულად შევინახოთ სიხშირე ელემენტებთან ერთად რუქაში.

შემდეგ ჩვენ დავაყენებთ მნიშვნელობას მაქსიფრეკი 0-მდე და მინფრეკი n– მდე, ანუ მასივის სიგრძე, რადგან არც ერთ ელემენტს არ აქვს სიხშირე მოცემული მასივის ზომაზე მეტი. ჩვენ გადავკვეთთ რუკას და თითოეულ ელემენტს სათითაოდ ავიღებთ და გადავამოწმებთ, აქვს თუ არა მას ყველაზე მაღალი ან ყველაზე დაბალი სიხშირე. ცალკეული მაქსიმალური სიხშირე სხვა ცვლადზე და მინიმალური სიხშირე სხვადასხვა ცვლადზე. ჩვენ უნდა დავაბრუნოთ სხვაობა მაქსიმალურ სიხშირესა და ყველაზე დაბალ სიხშირეს შორის, ამიტომ დავბრუნდებით (maxfreq-minfreq).

ავიღოთ მაგალითი:

მაგალითი

arr [] = {1, 2, 3, 1, 5, 2, 3, 1}

როდესაც მასივი პირველად გადავკვეთთ, ელემენტს და მათ რაიმე შემთხვევას არ დავდებთ რუქაში, გადაკვეთის შემდეგ რუქა გვექნება:

რუკა: {1: 3, 2: 2, 3: 2, 5: 1}

ახლა ჩვენ გვაქვს თითოეული ელემენტის მოვლენები რუკაზე, ჩვენ ვაპირებთ გავკვეთოთ რუკაზე და ავიღოთ თითოეული ელემენტი რუქიდან და შეამოწმოთ მათი სიხშირე, რაც უფრო მეტი სიხშირეა ან maxfreq და რომელია მინიმალური მიმდინარე სიხშირე ან minfreq და შეინახეთ შესაბამისად maxfreq და minfreq.

  • 1: 3

3 მეტია ვიდრე maxfreq, ამიტომ maxfreq = 3

3 მცირეა ვიდრე minfreq, ამიტომ minfreq = 3

  • 2: 2

maxfreq 2-ზე მეტია, ასე რომ maxfreq = 3

2 მცირეა ვიდრე minfreq, ამიტომ minfreq = 2

  • 3: 2

maxfreq 2-ზე მეტია, ასე რომ maxfreq = 3

არაფერი შეცვლილა minfreq- ში, minfreq = 2

  • 5: 1

maxfreq 1-ზე მეტია, ასე რომ maxfreq = 3

1 მცირეა ვიდრე minfreq, ამიტომ minfreq = 1

და ჩვენ დავუბრუნებთ სხვაობას maxfreq-minfreq → (3-1) = 2-ს შორის.

კოდი

C ++ კოდი მასივის ყველაზე მაღალ და მინიმუმ სიხშირეებს შორის სხვაობის მოსაძებნად

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumDiff(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

ჯავის კოდი, რათა იპოვოთ განსხვავება მასივში ყველაზე მაღალ და მინიმუმ სიხშირეებს შორის

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. აქ ჩვენ უბრალოდ გადავკვეთეთ მასივის ელემენტები, რომლებიც თვალყურს ადევნებს მათ სიხშირეებს. ეს ყველაფერი მხოლოდ O (N) დრო ჯდება.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მაქსიმუმ, ჩვენ შეგვიძლია n ელემენტის შენახვა, თუ ყველა მათგანი გამორჩეულია. სივრცის სირთულე ხაზოვანია.