Computer >> Máy Tính >  >> Lập trình >> C ++

Tìm hoán vị nhỏ nhất của số đã cho trong C ++


Trong bài toán này, chúng ta được cho một số lớn N. Nhiệm vụ của chúng ta là tìm hoán vị nhỏ nhất của một số nhất định.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

N = 4529016

Đầu ra

1024569

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là lưu trữ giá trị số nguyên dài để làm nhỏ lại. Sau đó, chúng tôi sẽ sắp xếp chuỗi đó là kết quả của chúng tôi. Nhưng nếu có bất kỳ số 0 nào đang xếp chồng lên nhau, chúng tôi sẽ chuyển chúng sau giá trị khác 0 đầu tiên.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;
string smallestNumPer(string s) {
   int len = s.length();
   sort(s.begin(), s.end());
   int i = 0;
   while (s[i] == '0')
      i++;
   swap(s[0], s[i]);
   return s;
}
int main() {
   string s = "4529016";
   cout<<"The number is "<<s<<endl;
   cout<<"The smallest permutation of the number is "<<smallestNumPer(s);
   return 0;
}

Đầu ra

The number is 4529016
The smallest permutation of the number is 1024569