Leetcode-2048. Next larger numerical balance

link

2048. The next larger numerical equilibrium number

subject

If the whole number   x Satisfy ： For each digit  d , This digit   just stay x It appears that d Time . So integers x It's just one. Numerical equilibrium number .

Give you an integer n , Please return Strictly greater than n Of Minimum numerical equilibrium number .

Example

Example 1：
Input ：n = 1
Output ：22
explain ：
22 Is a numerical equilibrium number , because ：
- Numbers 2 appear 2 Time  
This is also strictly greater than 1 Minimum numerical equilibrium number of .

Example 2：
Input ：n = 1000
Output ：1333
explain ：
1333 Is a numerical equilibrium number , because ：
- Numbers 1 appear 1 Time .
- Numbers 3 appear 3 Time . 
This is also strictly greater than 1000 Minimum numerical equilibrium number of .
Be careful ,1022 Cannot be used as an answer to this input , Because the numbers 0 More than 0 .

Example 3：
Input ：n = 3000
Output ：3133
explain ：
3133 Is a numerical equilibrium number , because ：
- Numbers 1 appear 1 Time .
- Numbers 3 appear 3 Time . 
This is also strictly greater than 3000 Minimum numerical equilibrium number of

explain

• 0 <= n <= 10e6

Train of thought （ violence ）

Let's first understand the meaning of the topic , That means numbers n Can only appear n Time ,1 Can only appear 1 Time ,2 Can only appear 2 Time , Then you can arrange and combine these numbers , such as 1,22,212,221,3331,122333 wait , It's a question n The maximum is 10e6, So we can list all the minimum equilibrium numbers , Then judge directly

C++ Code

class Solution {
public:
        int nextBeautifulNumber(int n) {
        vector<int> num{1,22,122,212,221,333,1333,3133,3313,3331,4444,14444,22333,23233,23323,23332,32233,32323,32332,33223,33232,33322,41444,44144,44414,44441,
                55555,122333,123233,123323,123332,132233,132323,132332,133223,133232,133322,155555,212333,213233,213323,213332,221333,223133,223313,223331,224444,231233,231323,231332,
                232133,232313,232331,233123,233132,233213,233231,233312,233321,242444,244244,244424,244442,312233,312323,312332,313223,313232,313322,321233,321323,
                321332,322133,322313,322331,323123,323132,323213,323231,323312,323321,331223,331232,331322,332123,332132,332213,332231,332312,332321,333122,333212,333221,422444,
                424244,424424,424442,442244,442424,442442,444224,444242,444422,515555,551555,555155,555515,555551,666666,1224444};
        int p = num.size();
        for (int i = 0; i < p; i++) {
            if (n < num[i]) {
                return num[i];
            }
        }
        return 0;
    }
};

Train of thought two （ violence ）

The same violence , But we don't list all the minimum equilibrium numbers , But from n+1 The number of starts to judge one by one , Until the minimum equilibrium number is found .

C++ Code

class Solution {
public:
    bool check(int num){
        int cnt[10] = {0};
        while (num > 0) 
        {
            int temp = num % 10;
            cnt[temp]++;
            num = num / 10;
        }
        for (int i = 0; i < 10; i++) 
        {
            if (cnt[i] && cnt[i] != i) 
                return false;
        }
        return true;    
    }
    int nextBeautifulNumber(int n) {
        int num=n+1;
        while(check(num) == false) num++;
        return num;
    }
};