โซลูชัน Leetcode องค์ประกอบส่วนใหญ่ II


ระดับความยาก กลาง
ถามบ่อยใน อะโดบี อเมซอน แอปเปิล บลูมเบิร์ก Facebook Google ไมโครซอฟท์ Zenefits
แถว

ในปัญหานี้เราจะได้รับไฟล์ แถว จำนวนเต็ม เป้าหมายคือการค้นหาองค์ประกอบทั้งหมดที่เกิดขึ้นมากกว่า ⌊N / 3⌋ เวลาในอาร์เรย์โดยที่ N = ขนาดของอาร์เรย์และ⌊⌋เป็นตัวดำเนินการพื้น เราจำเป็นต้องส่งคืนอาร์เรย์ขององค์ประกอบดังกล่าว

ช่วงขององค์ประกอบ: -10 ^ 9 ไปยัง 10 9 ^

ตัวอย่าง

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

คำอธิบาย⌊N / 3⌋ = ⌊5 / 3⌋ = 1 ตอนนี้จำนวนเต็ม 2 และ 3 มีความถี่เท่ากับ 2 ซึ่งมากกว่า 1 ดังนั้นเราจึงพิมพ์มัน

Array = {1 , 2 , 3 , 4}
No majority elements

คำอธิบาย: เราไม่พบองค์ประกอบใด ๆ ที่มีความถี่มากกว่า 1 ในกรณีนี้ ดังนั้นเราจึงพิมพ์ "ไม่มีองค์ประกอบส่วนใหญ่"

วิธีการ (การจัดเก็บความถี่)

ตามชื่อเรื่องเราสามารถจัดเก็บความถี่ของทุกองค์ประกอบในอาร์เรย์โดยใช้ตารางแฮชจากนั้นตรวจสอบองค์ประกอบที่มีความถี่มากกว่า ⌊N / 3⌋. ด้วยวิธีนี้เราจะพบองค์ประกอบทั้งหมดที่ตรงตามเงื่อนไข

ขั้นตอนวิธี

  1. เริ่มต้น HashMapความถี่ เพื่อเก็บความถี่ขององค์ประกอบในอาร์เรย์และรายการ / เวกเตอร์ ผล เพื่อจัดเก็บองค์ประกอบส่วนใหญ่
  2. สำหรับทุกองค์ประกอบ ในอาร์เรย์:
    • เพิ่มความถี่: ความถี่ [i] ++ (หรือตั้งค่าเป็น 1 หากยังไม่มีอยู่)
  3. สำหรับทุกคน สำคัญ ในแฮชแมป:
    1. If ความถี่ [คีย์] > N / 3
      1. เพิ่มลงในไฟล์ ผล
  4. กลับรายการ ผล

การดำเนินการของ Majority Element II Leetcode Solution

โปรแกรม C ++

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

vector<int> majorityElement(vector<int>& a)
{
    int N = a.size();
    vector <int> result;
    unordered_map <int , int> frequency;
    for(int &x : a)
        frequency[x]++;
    for(auto &x : frequency)
        if(x.second > N / 3)
            result.emplace_back(x.first);
    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

โปรแกรม Java

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashMap <Integer , Integer> frequency = new HashMap <>();

        for(int i = 0 ; i < a.length ; i++)
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);

        for(Map.Entry i : frequency.entrySet())
        {
            Integer value = (int)i.getValue() , key = (int)i.getKey();
            if((int)value > ((a.length) / 3))
                result.add(key);
        }
        return result;
    }
}
2 3

การวิเคราะห์ความซับซ้อนของ Majority Element II Leetcode Solution

ความซับซ้อนของเวลา

บน) เมื่อเราสำรวจอาร์เรย์ทั้งหมดหนึ่งครั้งเพื่ออัปเดตความถี่ N = ขนาดของอาร์เรย์

ความซับซ้อนของอวกาศ

บน) ในขณะที่เราใช้ตารางแฮชเพื่อจัดเก็บความถี่

แนวทาง (ขั้นตอนวิธีการโหวต Boyer-Moore)

สิ่งแรกที่ต้องสังเกตก็คือสามารถมีได้สูงสุด 2 องค์ประกอบที่มีความถี่มากกว่า ⌊N / 3⌋ในอาร์เรย์ ดังนั้นปัญหานี้จะเหมือนกับไฟล์ องค์ประกอบเสียงข้างมาก ปัญหากับ 2 องค์ประกอบส่วนใหญ่ในครั้งนี้

เราได้แก้ไขปัญหา Majority Element แล้วโดยใช้อัลกอริทึมการโหวตของ Boyer-Moore ในกรณีขององค์ประกอบส่วนใหญ่เราสามารถใช้อัลกอริทึมโดยการเปรียบเทียบว่าองค์ประกอบปัจจุบันเป็นตัวเลือกหรือไม่ แต่ในกรณีนี้เราจำเป็นต้องมีองค์ประกอบส่วนใหญ่ที่เป็นไปได้สององค์ประกอบและอัปเดตตัวนับควบคู่กันไป ด้วยความช่วยเหลือของสัญชาตญาณนี้เราสามารถกำหนดเงื่อนไขของเราได้ดังนี้:

  • ตั้งค่าผู้สมัครแบบสุ่มสองตัวใด ๆ นอกช่วงขององค์ประกอบในอาร์เรย์
  • หากองค์ประกอบเท่ากับผู้สมัครคนใดคนหนึ่งให้เพิ่มตัวนับ
  • ถ้าตัวนับของผู้สมัครหนึ่งคนเท่ากับ 0 ณ จุดใดก็ตามเราตั้งค่าองค์ประกอบปัจจุบันเป็นตัวเลือก if องค์ประกอบปัจจุบันนี้ไม่ใช่ผู้สมัครรายอื่น
  • เราจะลดจำนวนตัวนับของผู้สมัครทั้งสองหากองค์ประกอบปัจจุบันไม่เท่ากับผู้สมัครคนใดคนหนึ่ง

ด้วยวิธีนี้เรายังคงรักษาผู้สมัครสองคนที่แตกต่างกันในอาร์เรย์โดยที่ผู้สมัครคนแรกส่งผลกระทบต่ออีกคน อย่างไรก็ตามเป็นไปได้ว่าผู้สมัครที่เราลงท้ายด้วยไม่ใช่องค์ประกอบส่วนใหญ่ที่แท้จริง ({1, 1, 2, 2, 3, 3} เป็นตัวอย่างหนึ่ง) ดังนั้นจึงจำเป็นต้องเรียกใช้บัตรผ่านที่สองเพื่อนับความถี่ของผู้สมัครที่เราลงเอยด้วย ด้วยเหตุนี้เราจึงสามารถส่งคืนเวกเตอร์ขององค์ประกอบส่วนใหญ่ได้

ขั้นตอนวิธี

  1. เริ่มต้น candOne และ candtwo เพื่อจัดเก็บผู้สมัครสองคนและความถี่ของพวกเขา cntOne และ cntTwo as 0.
  2. สำหรับทุกองค์ประกอบ ในอาร์เรย์:
    • If candOne == ฉัน:
      • cntOne++
    • อื่นถ้า candTwo == i
      • cntTwo++
    • อื่นถ้า cnหนึ่ง == 0
      • กำหนด i as candOne: candOne = ฉัน
      • ตั้งค่าการนับเป็น 1: cntOne = 1
    • อื่นถ้า cntTwo == 0
      • candTwo = ฉัน
      • cntTwo = 1
    • จำนวนผู้สมัครทั้งสองที่ลดลง:
      • cntOne–
      • cntTwo–
  3. ตั้งค่าการนับกลับเป็นศูนย์สำหรับรอบที่สอง: cntOne = 0 และ cntTwo = 0
  4. สำหรับทุกองค์ประกอบในอาร์เรย์:
    • ถ้ามันเท่ากับ candOne:
      • cntOne ++
    • อื่นถ้ามันเท่ากับ candTwo:
      • cntTwo ++
  5. เริ่มต้นรายการ / เวกเตอร์ ผล เพื่อจัดเก็บองค์ประกอบส่วนใหญ่
  6. ถ้า cntOne> N / 3
    • ผลัก candOne ไปยัง ผล
  7. ถ้า cntTwo> N / 3
    • ผลัก candTwo ไปยัง ผล
  8. พิมพ์ผลลัพธ์

ภาพประกอบ:

โซลูชัน Leetcode องค์ประกอบส่วนใหญ่ II

การดำเนินการของ Majority Element II Leetcode Solution

โปรแกรม C ++

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

vector <int> majorityElement(vector <int> &a)
{
    vector <int> result;
    int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
    for(int &i : a)
    {
        if(candOne == i)
            cntOne++;
        else if(candTwo == i)
            cntTwo++;
        else if(cntOne == 0)
        {
            candOne = i;
            cntOne++;
        }
        else if(cntTwo == 0)
        {
            candTwo = i;
            cntTwo++;
        }
        else
        {
            cntOne--;
            cntTwo--;
        }
    }

    cntOne = 0;
    cntTwo = 0;
    for(int &i : a)
    {
        if(i == candOne)
            cntOne++;
        if(i == candTwo)
            cntTwo++;
    }

    if(cntOne > ((int)a.size()) / 3)
        result.push_back(candOne);
    if(cntTwo > ((int)a.size()) / 3)
        result.push_back(candTwo);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

โปรแกรม Java

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList<>();

        int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
        for(int i : a)
        {
            if(candOne == i)
                cntOne++;
            else if(candTwo == i)
                cntTwo++;
            else if(cntOne == 0)
            {
                candOne = i;
                cntOne++;
            }
            else if(cntTwo == 0)
            {
                candTwo = i;
                cntTwo++;
            }
            else
            {
                cntOne--;
                cntTwo--;
            }
        }

        cntOne = 0;
        cntTwo = 0;
        for(int i : a)
        {
            if(i == candOne)
                cntOne++;
            if(i == candTwo)
                cntTwo++;
        }

        if(cntOne > (a.length) / 3)
            result.add(candOne);
        if(cntTwo > (a.length) / 3)
            result.add(candTwo);

        return result;
    }
}
3 2

การวิเคราะห์ความซับซ้อนของ Majority Element II Leetcode Solution

ความซับซ้อนของเวลา

บน) เมื่อเรารันอาร์เรย์สองรอบโดยไม่คำนึงถึงอินพุต N = ขนาดของอาร์เรย์

ความซับซ้อนของอวกาศ

O (1) เมื่อเรามีพื้นที่หน่วยความจำคงที่