จัดเรียงจำนวนเต็มตามค่ากำลังใน C++

อย่างที่เราทราบดีว่ากำลังของจำนวนเต็ม x ถูกกำหนดให้เป็นจำนวนขั้นตอนที่จำเป็นในการแปลง x เป็น 1 โดยใช้ขั้นตอนต่อไปนี้ -

• ถ้า x เป็นคู่ x =x / 2

• ถ้า x เป็นเลขคี่ x =3 * x + 1

ตัวอย่างเช่น พลังของ x =3 คือ 7 เพราะ 3 ใช้ 7 ขั้นตอนกลายเป็น 1 (3 → 10 → 5 → 16 → 8 → 4 → 2 → 1) ถ้าเรามีจำนวนเต็ม lo, hi และ k เราต้องจัดเรียงจำนวนเต็มทั้งหมดในช่วงเวลา [lo, hi] โดยค่ากำลังในการเรียงลำดับจากน้อยไปมาก ตอนนี้ ถ้าจำนวนเต็มตั้งแต่สองตัวขึ้นไปมีค่ากำลังเท่ากัน ให้เรียงลำดับจากน้อยไปหามาก เราต้องหาจำนวนเต็มที่ k ในช่วง [lo, hi] เรียงตามค่ากำลัง

ตัวอย่างเช่น หากอินพุตเป็น lo =12, hi =15 และ k =2 ดังนั้นเอาต์พุตจะเป็น 13 เนื่องจากกำลังของ 12 คือ 9, กำลังของ 13 คือ 9 สำหรับ 14 นี่คือ 17 และสำหรับ 15 มันก็เป็น 17 ด้วย ดังนั้นลำดับการจัดเรียงคือ [12,13,14,15] และเมื่อ k =2 ดังนั้นองค์ประกอบคือ 13

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

• กำหนดเมธอด getTurn ซึ่งจะใช้ n เป็นอินพุต

• ยกเลิก :=0

• ในขณะที่ n ไม่ใช่ 1

  • ถ้า n เป็นเลขคี่ ดังนั้น n :=n * 3 + 1 มิฉะนั้น n :=n / 2

  • เพิ่มขึ้น 1

• จากวิธีหลัก

• เพราะฉันอยู่ในช่วง lo ถึง hi

  • สร้างคู่ (getTurn(i), i)

  • ใส่ temp ลงใน ret

• เรียงคู่ตามกำลัง หรือเรียงลำดับจากน้อยไปมาก

• ส่งคืนค่าที่สองของคู่ ret[k - 1]

ตัวอย่าง (C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector < pair <int, int> > ret;
   static bool cmp(pair <int, int>& a, pair <int, int>& b){
      return a.first == b.first ? a.second < b.second : a.first < b.first;
   }
   int getTurn(int n){
      int ret = 0;
      while(n != 1){
         if(n & 1){
            n = n * 3 + 1;
         }
         else n >>= 1;
            ret ++;
      }
      return ret;
   }
   int getKth(int lo, int hi, int k) {
      for(int i = lo; i <= hi; i++){
         pair <int, int> temp;
         temp.first = getTurn(i);
         temp.second = i;
         ret.push_back(temp);
      }
      sort(ret.begin(), ret.end(), cmp);
      return ret[k - 1].second;
   }
};
main(){
   Solution ob;
   cout << (ob.getKth(12, 15, 2));
}

อินพุต

12
15
2

ผลลัพธ์

13