Find All Duplicates in an Array ใน C++

ตัวอย่าง: nums = [4,3,2,7,8,2,3,1]

ตัวที่ซ้ำ: 2 และ 3 → ผลลัพธ์: [2, 3]

อัลกอริทึม: Index Marking (Negation Trick)

ใช้ข้อเท็จจริงว่า 1 ≤ nums[i] ≤ n → สามารถใช้ index nums[i] - 1 เป็นตัวบ่งชี้

1. วนลูป i = 0..n-1:
   • x = abs(nums[i]) (ค่าตัวเลข)
   • idx = x - 1 (index ที่สอดคล้อง)
   • หาก nums[idx] < 0 → หมายถึงเคยมาที่ index นี้แล้ว → x เป็น duplicate → เพิ่มในผลลัพธ์
   • มิฉะนั้น nums[idx] *= -1 (ทำเครื่องหมายว่าเจอแล้ว)

การทำเครื่องหมายเป็นลบ (negation) ใช้ bit sign bit เป็น flag โดยไม่ต้องการพื้นที่เพิ่ม

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

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

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

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            int x = abs(nums[i]);
            int idx = x - 1;
            if (nums[idx] < 0) {
                ans.push_back(x);
            } else {
                nums[idx] *= -1;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {4, 3, 2, 7, 8, 2, 3, 1};
    print_vector(ob.findDuplicates(v));
    return 0;
}

Input

[4,3,2,7,8,2,3,1]

Output

[2, 3]

ความซับซ้อน (Complexity)

• เวลา: O(n)
• พื้นที่: O(1) เพิ่มเติม (แก้ไขอาร์เรย์ต้นทางในที่)

ข้อควรระวัง: วิธีนี้ เปลี่ยนแปลงอาร์เรย์ต้นทาง** หากต้องรักษาค่าเดิม ต้องคัดลอกก่อน หรือใช้วิธีอื่น (เช่น cyclic sort, หรือ Floyd's Tortoise and Hare สำหรับหาตัวซ้ำ 1 ตัว)