ช่วงที่หายไปใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็มที่เรียงแล้ว nums ช่วงขององค์ประกอบอยู่ในช่วงรวม [lower, upper] เราต้องหาช่วงที่หายไป

ตัวอย่าง: nums = [0, 1, 3, 50, 75], lower = 0, upper = 99 ผลลัพธ์: ["2", "4->49", "51->74", "76->99"]

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

1. ลบค่าซ้ำใน nums (ถ้ามี)
2. ใช้ตัวแปร curr เริ่มจาก lower
3. เปรียบเทียบ curr กับ nums[i]:
   • เท่ากัน: curr++, i++
   • ไม่เท่ากัน: นับช่วงที่หายไปจนกว่าจะเจอ nums[i] หรือครบ upper
4. จัดรูปแบบผลลัพธ์: ตัวเลขเดียวหรือ "start->end"

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

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

void print_vector(vector<string> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 

class Solution { 
public: 
    vector<string> findMissingRanges(vector<int>& t, int lower, int upper) { 
        vector<int> nums; 
        set<long long int> v; 
        for(int i = 0; i < t.size(); i++){ 
            if(!v.count(t[i])){ 
                v.insert(t[i]); 
                nums.push_back(t[i]); 
            } 
        } 
        vector<string> ret; 
        long long int curr = lower; 
        int i = 0; 
        int n = nums.size(); 
        while(curr <= upper){ 
            if(i < n && nums[i] == curr){ 
                i++; 
                curr++; 
            } else { 
                string temp = to_string(curr); 
                curr++; 
                if(i < n && nums[i] == curr){ 
                    ret.push_back(temp); 
                    continue; 
                } else { 
                    if(i == n){ 
                        if(curr <= upper){ 
                            temp += "->"; 
                            temp += to_string(upper); 
                            curr = (long long int)upper + 1; 
                        } 
                        ret.push_back(temp); 
                    } else { 
                        temp += "->"; 
                        curr = nums[i]; 
                        temp += to_string(curr - 1); 
                        curr = nums[i]; 
                        ret.push_back(temp); 
                    } 
                } 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {0,1,3,50,75}; 
    print_vector(ob.findMissingRanges(v, 0, 99)); 
}

ข้อมูลนำเข้า

{0,1,3,50,75}, 0, 99

ผลลัพธ์

[2, 4->49, 51->74, 76->99, ]