首页 > 后端开发 > C++ > 根据数字的优先级,翻译如下:基于数字优先级的下一个更大的数字

根据数字的优先级,翻译如下:基于数字优先级的下一个更大的数字

王林
发布: 2023-08-28 08:45:10
转载
1233 人浏览过

根据数字的优先级,翻译如下:基于数字优先级的下一个更大的数字

在正常的数字系统中,0是最小的数字,而9是最大的数字。在这个问题中,我们将得到一个长度为10的列表,从索引0到索引9表示一个数字,它表示该数字的优先级,列表将按照递增顺序排列,这意味着出现在最后索引的数字具有最高的优先级。我们还将得到一个数字,我们需要找到比当前数字稍大的下一个数字。

Input 1: 
Given number = “123”
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132
登录后复制

Explanation

从给定的优先级数组中,我们可以看到1的优先级大于2和3。与2相比,3的优先级更高。因此,如果给定数字的下一个排列将通过交换2和3来实现。

Input 2:
Given number = 132
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132
登录后复制

Explanation

From the given priority array, we can see that the priority of 1 is greater than both 2 and 3. Priority of 3 is greater as compared to of 2. So, there will be no next permutation available.

方法

In this approach, we will use the concept of the standard template library (STL) provided by the C++ programming language to get the next permutation. Let us see the steps −

  • 首先,我们将得到下一个数字的数字,以及一个按升序表示数字优先级的数组。

  • 我们将调用预定义的函数来找到大于当前给定数字的下一个数字。

  • We will define a function that take the parameter given number and array.

  • We will define a global array and store the priority of each digit taken from the given array to use later.

  • 我们将把给定的数字转换为字符串,以便在其上应用下一个排列函数。

  • We will define a custom function that will used to compare the characters of the string in the next permutation function of the stl.

  • 获取下一个排列后,我们将把字符串转换为整数并返回。

Example

的中文翻译为:

示例

#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;
}
登录后复制

Output

The next number or permutation for the given number is: 123
登录后复制

Time and Space Complexity

The time complexity of the above code is O(N), where N is the number of digits in the given number.

The space complexity of the above code is O(N) because we are creating a new string to use the next permutation function.

Note: If the current number is the greater number among all the permutations then the next permutation function will return false and we will return the same number as the next permutation does not exist.

结论

在本教程中,我们实现了一个代码来找到下一个数字,该数字比当前数字大,但数字的优先级不是从0到9的顺序,而是在单独的数组中给出。我们使用了STL函数next_permutation和一个自定义函数来根据新的优先级获取下一个数字。以上代码的时间和空间复杂度为O(数字的位数)。

以上是根据数字的优先级,翻译如下:基于数字优先级的下一个更大的数字的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板