下一个更大的数字基于数字的优先级-yiteyi-C++库

给定一个数字号码包含 N 数字。问题是要用同一组数字来寻找下一个更大的数字号码基于给定的数字优先级。例如，数字的优先级如下所示： 1, 6, 4, 5, 2, 9, 8, 0, 7, 3 也就是说 1 < 6 < 4 < 5 < 2 < 9 < 8 < 0 < 7 < 3 .如果无法形成下一个更大的数字，则打印原始数字。

null

例如：

Input : num = "231447"        pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3}Output : 237144According to the precedence of digits 1 is being considered as the smallest digit and 3is being considered as the largest digit.Input : num = "471"        pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3}Output : 471

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 以下是步骤：

创建一个 优先权[] 大小为“10”的数组。借助于优先数组 前[] 为中的每个数字分配一个优先级编号 优先权[] 其中“1”被视为最小优先级，“10”被视为最高优先级。
使用 STL C++ NXTI置换使用手动定义的比较函数，查找下一个更大的排列。

C++

                         // C++ implementation to find the next greater number                       
                         // on the basis of precedence of digits                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         #define DIGITS 10                       
           
                         // priority[] to store the priority of digits                       
                         // on the basis of pre[] array. Here '1' is being                       
                         // considered as the smallest priority as '10' as                       
                         // the highest priority                       
                         int                                     priority[DIGITS];                       
           
                         // comparator function used for finding the                       
                         // the next greater permutation                       
                         struct                                     compare {                       
                                                 bool                                     operator()(                                     char                                     x,                                     char                                     y) {                       
                                                 return                                     priority[x -                                     '0'                                     ] < priority[y -                                     '0'                                     ];                       
                                                 }                       
                         };                       
           
                         // function to find the next greater number                       
                         // on the basis of precedence of digits                       
                         void                                     nextGreater(                                     char                                     num[],                                     int                                     n,                                     int                                     pre[]) {                       
                                                 memset                                     (priority, 0,                                     sizeof                                     (priority));                       
           
                                                 // variable to assign priorities to digits                       
                                                 int                                     assign = 1;                       
           
                                                 // assigning priorities to digits on                       
                                                 // the basis of pre[]                       
                                                 for                                     (                                     int                                     i = 0; i < DIGITS; i++) {                       
                                                 priority[pre[i]] = assign;                       
                                                 assign++;                       
                                                 }                       
           
                                                 // find the next greater permutation of 'num'                       
                                                 // using the compare() function                       
                                                 bool                                     a = next_permutation(num, num + n, compare());                       
           
                                                 // if the next greater permutation does not exists                       
                                                 // then store the original number back to 'num'                       
                                                 // using 'pre_permutation'.                       
                                                 if                                     (a ==                                     false                                     )                       
                                                 prev_permutation(num, num + n, compare());                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main() {                       
                                                 char                                     num[] =                                     "231447"                                     ;                       
                                                 int                                     n =                                     strlen                                     (num);                       
                                                 int                                     pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3};                       
                                                 nextGreater(num, n, pre);                       
                                                 cout <<                                     "Next Greater: "                                     << num;                       
                                                 return                                     0;                       
                         }                       

输出：

Next Greater: 237144

时间复杂度：O（n）。辅助空间：O（1）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章