ספירת פתרון ה- Leetcode הקבוצתי הגדול ביותר


רמת קושי קַל
נשאל לעתים קרובות מרצרי
מערך

הבעיה פתרון Leetcode Group Complete Group מספק לנו מספר שלם. אנו נדרשים למצוא את סכום הספרות של כל מספר בין 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 היא.

גישה

הבעיה ספירת קבוצה הגדולה ביותר Leetcode פתרון סיפק לנו מספר שלם אחד. וביקשנו לספור את מספר קבוצות המספרים עם התדירות המרבית שבה אנו מקבצים את המספרים לפי סכום הספרות שלהם. מכיוון שהקלט הוא אילוץ למקסימום של 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 (N) מכיוון שהלולאה הראשונה פועלת תלויה בקלט. לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

O (1), מכיוון שיש לנו מערך גודל קבוע. לפיכך מורכבות החלל נותרת קבועה ללא קשר לקלט.