Large to Small Sort in C++: เรียงสลับระหว่างค่ามากและน้อย

กำหนด array ของจำนวนเต็ม ต้องเรียงลำดับแบบสลับกันระหว่างค่ามากและน้อย:

• ตัวแรก = ค่าสูงสุด
• ตัวที่สอง = ค่าต่ำสุด
• ตัวที่สาม = ค่าสูงสุดอันดับ 2
• ตัวที่สี่ = ค่าต่ำสุดอันดับ 2
• ... และทำต่อไป

ตัวอย่าง: [6,3,10,4] → [10, 3, 6, 4]

วิธีแก้ปัญหา

1. เรียง array จากน้อยไปมาก
2. ใช้ two pointers: i ชี้ต้น (ค่าน้อย), j ชี้ท้าย (ค่ามาก)
3. สลับกัน push nums[j] แล้ว nums[i] จนกว่า i > j

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> solve(vector<int>& nums) {
        vector<int> ret;
        sort(nums.begin(), nums.end());
        int i = 0, j = nums.size() - 1;
        while(i <= j) {
            ret.push_back(nums[j--]);
            if(i <= j) ret.push_back(nums[i++]);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {6,3,10,4};
    // print result...
}

Input

{6,3,10,4}

Output

10, 3, 6, 4