資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
