โปรแกรมรับการเปลี่ยนจำนวนเต็มถัดไปของตัวเลขใน C++

สมมติว่าเรามีตัวเลข n เราต้องหาการเรียงสับเปลี่ยนที่ใหญ่กว่าถัดไปของตัวเลข เมื่อ n อยู่ในการเรียงสับเปลี่ยนที่ใหญ่ที่สุดอยู่แล้ว ให้หมุนลงไปที่การเรียงสับเปลี่ยนที่เล็กที่สุด

ดังนั้น หากอินพุตเท่ากับ n =319 เอาต์พุตจะเป็น 391

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน makeArray() ซึ่งจะใช้ x

• กำหนดอาร์เรย์ ret

• ในขณะที่ x ไม่ใช่ศูนย์ ให้ทำ -

  • ใส่ x mod 10 ที่ท้าย ret

  • x :=x / 10

• ย้อนกลับอาร์เรย์ ret

• รีเทิร์น

• กำหนดฟังก์ชั่นรวม () สิ่งนี้จะใช้อาร์เรย์ v

• ยกเลิก :=0

• สำหรับแต่ละองค์ประกอบ i ใน v

  • ret :=ret * 10

  • ret :=ret + ผม

• รีเทิร์น

• กำหนดฟังก์ชัน getIndex() ซึ่งจะใช้อาร์เรย์ v

• ถอยหลัง :=-1

• สำหรับการเริ่มต้น i :=ขนาดของ v เมื่อ i>=1 อัปเดต (ลด i โดย 1) ทำ -

  • ถ้า v[i]> v[i - 1] แล้ว −

    • ret :=ฉัน

    • ออกจากวง

• ถ้า ret ไม่เท่ากับ -1 แล้ว −

  • x :=v[ret - 1]

  • idx :=ยกเลิก

  • สำหรับการเริ่มต้น j :=ret + 1 เมื่อ j <ขนาดของ v อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

    • ถ้า v[j] x แล้ว −

      • idx :=เจ

  • แลกเปลี่ยน v[ret - 1] และ v[idx]

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดอาร์เรย์ v :=makeArray(num)

• idx :=getIndex(v)

• ถ้า idx เหมือนกับ -1 แล้ว −

  • จัดเรียงอาร์เรย์ v

• มิฉะนั้น

  • จัดเรียงอาร์เรย์ v

• ผลตอบแทนรวม(v)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> makeArray(int x) {
      vector<int> ret;
      while (x) {
         ret.push_back(x % 10);
         x /= 10;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
   int combine(vector<int>& v) {
      int ret = 0;
      for (int i : v) {
         ret *= 10;
         ret += i;
      }
      return ret;
   }
   int getIndex(vector& v) {
      int ret = -1;
      for (int i = v.size() - 1; i >= 1; i--) {
         if (v[i] > v[i - 1]) {
            ret = i;
            break;
         }
      }
      if (ret != -1) {
         int x = v[ret - 1];
         int idx = ret;
         for (int j = ret + 1; j < v.size(); j++) {
            if (v[j] < v[idx] && v[j] > x) {
               idx = j;
            }
         }
         swap(v[ret - 1], v[idx]);
      }
      return ret;
   }
   int solve(int num) {
      vector<int> v = makeArray(num);
      int idx = getIndex(v);
      if(idx == -1) {
         sort(v.begin(), v.end());
      }
      else {
         sort(v.begin() + idx, v.end());
      }
      return combine(v);
   }
};
int solve(int n) {
   return (new Solution())->solve(n);
}
int main(){
   int n = 319;
   cout << solve(n);
}

อินพุต

319

ผลลัพธ์

391