นับโซลูชัน Leetcode กลุ่มที่ใหญ่ที่สุด


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Mercari
แถว

ปัญหา Count Complete Group Leetcode Solution ให้เรามีจำนวนเต็ม เราจะต้องค้นหาผลรวมของตัวเลขแต่ละตัวระหว่าง 1 ถึง n (รวม) จากนั้นเราจะจัดกลุ่มตัวเลขที่มีผลรวมของหลักเดียวกันและทำการนับ จากนั้นเราต้องคำนวณจำนวนกลุ่มด้วยจำนวนสูงสุด ดูเหมือนจะสับสนในตอนแรก ลองมาดูตัวอย่างเล็ก ๆ น้อย ๆ

ตัวอย่าง

นับโซลูชัน Leetcode กลุ่มที่ใหญ่ที่สุด

n = 13
4

คำอธิบาย: ตัวเลขที่จัดกลุ่มตามผลรวมของตัวเลขคือ [1, 10], [2,11], [3,12], [4,13], [5], [6], [7], [ 8], [9]. ดังนั้นจึงมี 4 กลุ่มที่มีความถี่สูงสุดเป็น 2 ดังนั้นคำตอบคือ 4

n = 2
2

คำอธิบาย: ในทำนองเดียวกันถ้าคุณเห็นตัวเลขจนถึง 2 มีเพียง 2 ตัวเลขคือ 1 และ 2 ทั้งสองสร้างกลุ่มที่มีหมายเลขเดียวแต่ละหมายเลข ดังนั้นคำตอบคือ 2 กลุ่มที่มีความถี่สูงสุด 1

เข้าใกล้

ปัญหา Count Largest Group Leetcode Solution ทำให้เรามีจำนวนเต็มเดียว และขอให้นับจำนวนกลุ่มของตัวเลขที่มีความถี่สูงสุดที่เราจัดกลุ่มตัวเลขตามผลรวมของตัวเลข เนื่องจากอินพุตเป็นข้อ จำกัด สูงสุด 10000 เราจึงสร้างไฟล์ แถว เพื่อรักษาความถี่ของผลรวมของตัวเลข ขนาดสูงสุดของ CNT อาร์เรย์ควรเป็น 36 เนื่องจากอินพุตที่มีผลรวมสูงสุดจะเป็น 36 ดังนั้นเราจึงจำลองกระบวนการหาผลรวมของตัวเลขแต่ละตัวตั้งแต่ 1 ถึง n ในระหว่างการประเมินความถี่เราจะจัดเก็บความถี่สูงสุดที่คำนวณได้จนถึงขณะนี้ ตอนนี้เราเริ่มลูปใหม่และนับจำนวนกลุ่มที่มีความถี่สูงสุด

รหัสสำหรับการนับโซลูชัน Leetcode กลุ่มที่ใหญ่ที่สุด

รหัส C ++

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

int sumDigits(int n){
    int sum = 0;
    while(n>0){
        sum += (n%10);
        n /= 10;
    }
    return sum;
}

int countLargestGroup(int n) {
    int cnt[37];
    memset(cnt, 0, sizeof cnt);
    int mx = 0;
    for(int i=0;i<=n;i++){
        int s = sumDigits(i);
        cnt[s]++;
        if(cnt[s] > mx)
            mx = cnt[s];
    }
    
    int ans = 0;
    for(int i=0;i<37;i++){
        if(cnt[i] == mx)
            ans++;
    }
    return ans;
}

int main(){
    cout<<countLargestGroup(13);
}
4

รหัส Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static int sumDigits(int n){
        int sum = 0;
        while(n>0){
            sum += (n%10);
            n /= 10;
        }
        return sum;
    }

    public static int countLargestGroup(int n) {
        int cnt[] = new int[37];
        for(int i=0;i<37;i++)cnt[i] = 0;
        int mx = 0;
        for(int i=1;i<=n;i++){
            int s = sumDigits(i);
            cnt[s]++;
            if(cnt[s] > mx)
                mx = cnt[s];
        }

        int ans = 0;
        for(int i=0;i<37;i++){
            if(cnt[i] == mx)
                ans++;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.print(countLargetGroup(13));
    }
    
}
4

การวิเคราะห์ความซับซ้อน

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

บน), เนื่องจากลูปแรกทำงานขึ้นอยู่กับอินพุต ดังนั้นความซับซ้อนของเวลาจึงเป็นเชิงเส้น

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

O (1), เนื่องจากเรามีอาร์เรย์ขนาดคงที่ ดังนั้นความซับซ้อนของพื้นที่จึงคงที่โดยไม่คำนึงถึงอินพุต