LeetCode Contains Duplicate III：排序 + 二分查找解法

題目

給定整數陣列 nums，判斷是否存在兩個不同索引 i 和 j，使得 abs(nums[i] - nums[j]) <= t 且 abs(i - j) <= k。

思路

先用結構體儲存每個數字的值與原始索引，按值排序。接著遍歷排序後的陣列，對於每個元素 nums[i]，利用二分查找在其左側找到第一個值大於 nums[i].val - t - 1 的位置。然後檢查該範圍內是否有元素的原始索引差值在 k 以內。若存在則返回 true。

代碼 (C++)

struct Num { int pos, val; };

int partition(Num* nums, int l, int r) {
    int pivotVal = nums[l].val, pivotPos = nums[l].pos;
    while (l < r) {
        while (l < r && nums[r].val > pivotVal) r--;
        if (l < r) nums[l++] = nums[r];
        while (l < r && nums[l].val < pivotVal) l++;
        if (l < r) nums[r--] = nums[l];
    }
    nums[l].val = pivotVal; nums[l].pos = pivotPos;
    return l;
}

void quickSort(Num* nums, int l, int r) {
    if (l < r) {
        int mid = partition(nums, l, r);
        quickSort(nums, l, mid - 1);
        quickSort(nums, mid + 1, r);
    }
}

// 在非降序列中找第一個大於 target 的位置
int binarySearchFirstBigger(Num* nums, int l, int r, int target) {
    if (r - l + 1 == 0) return -1;
    while (l < r) {
        int m = l + ((r - l) >> 1);
        if (nums[m].val <= target) l = m + 1;
        else r = m;
    }
    return (nums[r].val > target) ? r : -1;
}

bool containsNearbyAlmostDuplicate(int* nums, int numsSize, int k, int t) {
    Num* arr = (Num*)malloc(sizeof(Num) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        arr[i].pos = i; arr[i].val = nums[i];
    }
    quickSort(arr, 0, numsSize - 1);
    for (int i = 1; i < numsSize; i++) {
        int minPos = binarySearchFirstBigger(arr, 0, i - 1, arr[i].val - t - 1);
        if (minPos != -1) {
            for (int j = minPos; j < i; j++) {
                if (abs(arr[i].pos - arr[j].pos) <= k) {
                    free(arr); return true;
                }
            }
        }
    }
    free(arr); return false;
}