LeetCode Contains Duplicate III

LeetCode Contains Duplicate III

LeetCode Contains Duplicate III

題目

思路

我的方法是先用一個結構體，存下每個數字的值和其原坐標；
然後根據值大小排序；
接著遍歷每一個數字num[i].val;
利用二分查找找到剛好比num[i].val - t - 1大的數字的坐標；
然後根據坐標判斷是否存在值即可；
關於二分查找可見：Binary Search

代碼

struct num {
    int pos, val;
};

int AD(struct num * nums, int l, int r) {
    int K = nums[l].val;
    int Kp = nums[l].pos;
    while (l < r) {
        while (l < r && nums[r].val > K) r--;
        if (l < r) nums[l++] = nums[r];
        while (l < r && nums[l].val < K) l++;
        if (l < r) nums[r--] = nums[l];
    }
    nums[l].val = K;
    nums[l].pos = Kp;
    return l;
}

void QS(struct num * nums, int l, int r) {
    if (l < r) {
        int mid = AD(nums, l, r);
        QS(nums, l, mid - 1);
        QS(nums, mid + 1, r);
    }
}

// 在不下降的序列中尋找恰好比target大的數出現位置，也即第一個比target大的數出現的位置
int binarySearchIncreaseFirstBigger(struct 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;
    }
    if (nums[r].val > target) return r;
    else return -1;
}

bool containsNearbyAlmostDuplicate(int* nums, int numsSize, int k, int t) {
    struct num * N = (struct num*)malloc(sizeof(struct num) * numsSize);
    for (int i = 0; i < numsSize; i++) N[i].pos = i, N[i].val = nums[i];
    QS(N, 0, numsSize - 1);
    for (int i = 1; i < numsSize; i++) {
        int minPos = binarySearchIncreaseFirstBigger(N, 0, i - 1, N[i].val - t - 1);
        if (minPos == -1) {

        }
        else {
            for (int j = minPos; j < i; j++) {
                if (abs(N[i].pos - N[j].pos) <= k) {
                    free(N);
                    return true;
                }
            }
        }
    }
    free(N);
    return false;
}