ამოხსნის უმრავლესობის ელემენტი Leetcode


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Atlassian Bloomberg Facebook მიდი მამიკო Google microsoft Oracle განყოფილებაში Snapchat Yahoo ზენეფიტები
Დაყავი და იბატონე ჰაშინგი

პრობლემის განცხადება

ჩვენ გვაძლევენ მასივი მთელი რიცხვების. ჩვენ უნდა დავაბრუნოთ მთელი რიცხვი, რომელიც ხდება ⌊N / 2⌋ დროზე მეტი მასივში, სადაც ⌊ ⌋ არის იატაკის ოპერატორი. ამ ელემენტს უმრავლესობის ელემენტს უწოდებენ. გაითვალისწინეთ, რომ შეყვანის მასივი ყოველთვის შეიცავს უმრავლესობის ელემენტს.

მაგალითი

Array = {1 , 3 , 3 , 3}
3

ექსპლანაცია: ⌊N / 2⌋ = 4/2 = 2. და მთელი რიცხვი '3' მასივში ხდება 3-ჯერ.

Array = {1 , 1 , 2}
1

განმარტება: ⌊N / 2⌋ = 3 / 2⌋ = 1. მასივში '1' ხდება 2-ჯერ.

მიდგომა (hashtable)

შეგვიძლია მასივის ყველა ელემენტის სიხშირე შევინახოთ ჰეშის ცხრილში. ამის შემდეგ ადვილი ხდება სიხშირის მქონე მთელი რიცხვის შემოწმება> ⌊N / 2⌋.

ალგორითმი

  1. დაიწყეთ ჰეშის ცხრილი მასივში მთელი რიცხვების სიხშირის შესანახად: სიხშირე
  2. ყველა ელემენტისთვის, i, მასივში:
    • ზრდა სიხშირე [i] ან მითითებული სიხშირე [i] = 0 თუ ეს უკვე არ არის ცხრილში
    •  If სიხშირე [i] > N / 2:
      • დაბრუნება მე
  3. დაბრუნება -1 (შედგენის შეცდომის თავიდან ასაცილებლად)
  4. დაბეჭდე შედეგი

განხორციელება უმრავლესობის ელემენტის Leetcode გადაწყვეტა

C ++ პროგრამა

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

int majorityElement(vector <int> &a)
{
    int majorityCount = ((int) a.size()) / 2;
    unordered_map <int , int> frequency;
    for(int &i : a)
    {
        if(++frequency[i] > majorityCount)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

ჯავა პროგრამა

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        HashMap <Integer , Integer> frequency = new HashMap<>();
        for(int i = 0 ; i < a.length ; i++)
        {
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);
            if(frequency.get(a[i]) > a.length / 2)
                return a[i];
        }
        return -1;
    }
}
2

უმრავლესობის ელემენტის ლეეტკოდის ამოხსნის სირთულის ანალიზი

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

O (N) მას შემდეგ, რაც მასივს ერთხელ გადავკვეთთ, რომ იპოვოთ უმრავლესობის ელემენტი. N = მასივის ზომა.

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

O (N) როგორც მასივის მკაფიო ელემენტების მაქსიმალური რაოდენობა შეიძლება იყოს: N - ⌊N / 2⌋ როგორც უმრავლესობის ელემენტს მაინც იკავებს ⌊N / 2⌋ ინდექსები. ამიტომ, სივრცის სირთულე ხაზოვანია.

მიდგომა (ბოიერ-მურის ხმის მიცემის ალგორითმი)

ეს პრობლემა მშვენიერი ილუსტრაციაა იმისა, თუ როგორ შეგვიძლია უმრავლესობის ელემენტის პოვნა ელემენტების ნაკადში. ბოიერ-მურის ხმის მიცემის ალგორითმი გამოიყენება იმ ელემენტის მოსაძებნად, რომელიც თანმიმდევრობით ⌊N / 2⌋ ზე მეტ ადგილს იკავებს. ეს ალგორითმი ინარჩუნებს ა კანდიდატი და მისი იმედი მასივში. ჩვენ ვაწარმოებთ მასივის ერთ პასს კანდიდატი = -1 და იმედი = 0. თუ მასივის რომელიმე ელემენტია კანდიდატი, ჩვენ ვზრდით ითვლიან. წინააღმდეგ შემთხვევაში, ჩვენ მას ვამცირებთ. თუ რაოდენობა ნულდება, ჩვენ ვცვლით კანდიდატი და დააყენეთ მისი იმედი დავუბრუნდეთ 0-ს.

იმისათვის, რომ გაიგოთ მისი ფუნქციონირება, მიჰყევით ქვემოთ მოცემულ მაგალითს:

ამოხსნის უმრავლესობის ელემენტი Leetcode

ეს ალგორითმი მიიჩნევს პროცესს, როგორც არჩევნებს და პირველ რიგში გადაწყვეტს კანდიდატს. ის, ვინც მეტ ხმას მიიღებს, არის უმრავლესობის კანდიდატი. ზემოთ მოყვანილ მაგალითში, თავდაპირველად ვირჩევთ კანდიდატს 1-ით, მაგრამ მასივში 4-ს მივაღწიეთ, ჩვენ ვაკვირდებით ამ რიცხვს = 0, რაც ნიშნავს, რომ ვნახეთ იმდენი კანდიდატი, რამდენიც არაკანდიდატი. ასე რომ, ჩვენ ვირჩევთ მიმდინარე ელემენტს კანდიდატად და ვაგრძელებთ პროცესს. ვინაიდან ჩვენ ვართ გარანტირებული მასივში რომ გვქონდეს უმრავლესობის ელემენტი, ბოლო კანდიდატი, რომელიც დაგვრჩა, იქნება უმრავლესობის ელემენტი.

ალგორითმი

  1. ორი ცვლადის ინიციალიზაცია: კანდიდატი და cnt შესანახად კანდიდატი და მისი სიხშირე შესაბამისი განმეორებისათვის
  2. ახლა, ყველა ელემენტისთვის i მასივში:
    • If cnt ნულის ტოლია:
      • განახლების თარიღი: კანდიდატი = მე
    • If i უდრის კანდიდატი:
      • ზრდა cnt: cnt ++
    • სხვა:
      • შემცირება cnt: cnt–
  3. დაბრუნების კანდიდატი
  4. დაბეჭდე შედეგი

განხორციელება უმრავლესობის ელემენტის Leetcode გადაწყვეტა

C ++ პროგრამა

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

int majorityElement(vector <int> &a)
{
    int candidate = -1 , cnt = 0;
    for(int &i : a)
    {
        if(cnt == 0)
            candidate = i;
        cnt += (candidate == i) ? 1 : -1;
    }
    return candidate;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

ჯავა პროგრამა

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        int candidate = -1 , cnt = 0;
        for(int i = 0 ; i < a.length ; i++)
        {
            if(cnt == 0)
                candidate = a[i];
            cnt += (candidate == a[i]) ? 1 : -1;
        }
        return candidate;
    }
}
2

უმრავლესობის ელემენტის ლეეტკოდის ამოხსნის სირთულის ანალიზი

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

O (N) როგორც ჩვენ მთელი მასივი ერთხელ გადავკვეთთ. Აქ, N = მასივის ზომა.

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

O (1) რადგან ვიყენებთ მეხსიერების მუდმივ ადგილს.