数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究基于数字优先级的下一个更大数
在正常的数字系统中，0 是最小的数字，而 9 是最大的数字。在这个问题中，我们将得到一个长度为 10 的列表，从索引 0 到索引 9，它代表一个数字，表示该数字的优先级，并且列表将按升序排列，这意味着最后索引处的数字具有最高优先级。我们也将得到一个数字，并且我们必须找到下一个比当前数字大一点的数字。
Input 1:
Given number = “123”
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132
解释
从给定的优先级数组中，我们可以看到 1 的优先级大于 2 和 3。3 的优先级大于 2。因此，如果给定数字的下一个排列将通过交换 2 和 3 来实现。
Input 2:
Given number = 132
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132
解释
从给定的优先级数组中，我们可以看到 1 的优先级大于 2 和 3。3 的优先级大于 2。因此，将没有可用的下一个排列。
方法
在这种方法中，我们将使用 C++ 编程语言提供的标准模板库 (STL) 的概念来获取下一个排列。让我们看看步骤 -
首先，我们将得到要从中找到下一个数字的数字，以及一个指示数字优先级（按升序排列）的数组。
我们将调用预定义函数来查找下一个比当前给定数字大的数字。
我们将定义一个函数，该函数将获取给定数字和数组作为参数。
我们将定义一个全局数组，并存储从给定数组中获取的每个数字的优先级，以便稍后使用。
我们将给定数字转换为字符串，以便在其上应用下一个排列函数。
我们将定义一个自定义函数，该函数将用于在 stl 的下一个排列函数中比较字符串的字符。
获取下一个排列后，我们将字符串转换为整数并返回它。
示例
#include <bits/stdc++.h>
using namespace std;
// priority array or array in which the priority of each digit will be stored
int prio[10];
// defining the compare function
bool compare(char& a, char& b){
return prio[a-'0'] < prio[b-'0'];
}
// function to get the next permuatation
int nextNum(int n, int arr[]){
for(int i=0; i<10; i++){
prio[arr[i]] = i;
}
// converting the given number into string
string str = to_string(n);
// calling the next permuatation stl function for the given string we will compare by custom function
bool cur = next_permutation(str.begin(),str.end(),compare);
if(cur == false){
// indicating the next permutation does not exist
return n;
}
n = stoi(str); // converting string back to number
return n;
}
int main(){
int n = 312; // the given number
int arr[] = {9, 2, 3, 6, 8, 1, 0, 5, 4, 7}; // given array
cout<<"The next number or permutation for the given number is: "<<nextNum(n, arr);
return 0;
}
输出
The next number or permutation for the given number is: 123
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定数字中数字的个数。
上述代码的空间复杂度为 O(N)，因为我们正在创建一个新的字符串来使用下一个排列函数。
注意：如果当前数字是所有排列中最大的数字，则下一个排列函数将返回 false，我们将返回相同的数字，因为下一个排列不存在。
结论
在本教程中，我们实现了查找下一个比当前数字大一点的数字的代码，但数字的优先级将不是从 0 到 9 的相同顺序，而是将在单独的数组中给出。我们使用了 STL 函数 next_permutation 和一个自定义函数来根据新的优先级获取下一个数字。上述代码的时间和空间复杂度为 O(数字个数)。
95 次查看
