Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

題意

給一個整型數(shù)組，找到數(shù)組中是否存在兩個元素，它們的下標(biāo)差不超過k，元素值差不超過t。

分析

一開始對于每個元素，查找它后面k個元素是否與其值相差t以內(nèi)。這樣時間復(fù)雜度為O(kn)，不能過超長數(shù)組的測試。所以可能存在O(nlogn)的算法。我的做法如下：

• 首先給數(shù)組元素排序，并保留原有下標(biāo)。示例如下：

• 維護(hù)一個特殊的隊(duì)列（包括一個元素隊(duì)列和下標(biāo)隊(duì)列）。該隊(duì)列要求隊(duì)首和隊(duì)尾的元素值相差不超過t。具體操作：
• (1) 如隊(duì)列為空則當(dāng)前元素入隊(duì)。
• (2) 如隊(duì)頭元素值與當(dāng)前待入隊(duì)元素值的差超過t，隊(duì)頭元素出隊(duì)(因?yàn)榻?jīng)排序后，后面入隊(duì)的元素值只會比當(dāng)前元素更大，不可能出現(xiàn)與隊(duì)首元素值差小于t的情況，所以隊(duì)首元素已經(jīng)沒有繼續(xù)存在在隊(duì)列中的必要了)。
• (3) 如對頭元素值與當(dāng)前待入隊(duì)元素值的差不超過t，則檢查二者的下標(biāo)差，如小于k，返回true，否則當(dāng)前元素入隊(duì)。
• (4) 最后隊(duì)中剩余的元素只需比較隊(duì)首與隊(duì)尾的下標(biāo)值即可。
• 時間復(fù)雜度。顯然是排序的時間復(fù)雜度為O(nlogn)，維護(hù)隊(duì)列的過程每個元素出入隊(duì)列一次。為O(n)。故總時間復(fù)雜度O(nlogn)。

TLE代碼及AC代碼

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = i - 1; j >= 0 && j > i - k; --j) {
                if (abs(nums[i] - nums[j]) <= t) { return true; }
            }
        }
        return false;
    }
};
//Time Limit Exceeded
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (nums.empty()) return false;
        vector<int> order(nums.size());
        for (int i = 0; i != order.size(); ++i) {
            order[i] = i;
        }
        //sort nums and orders
        sortNumbers(nums, order, 0, nums.size() - 1);
        //push and pop
        queue<int> numsque;
        queue<int> orderque;
        //initialize queue
        numsque.push(nums[0]);
        orderque.push(order[0]);

        for (int i = 1; i < nums.size();) {
            if (numsque.empty()) {
                numsque.push(nums[i]);
                orderque.push(order[i]);
                ++i; continue;
            }
            int num = numsque.front();
            int ord = orderque.front();
            if (nums[i] > num + t) {
                numsque.pop();
                orderque.pop();

            } else {
                if (isOrderRangeSatisfactory(order[i], ord, k)) {
                    return true;
                } else {
                    numsque.push(nums[i]);
                    orderque.push(order[i]);
                    ++i;
                }
            }
        }

        int backOrder = orderque.back();
        int frontOrder = orderque.front();
        while (backOrder != frontOrder) {
            if (isOrderRangeSatisfactory(backOrder, frontOrder, k)) {
                break;
            }
            orderque.pop();
            frontOrder = orderque.front();
        }
        if (backOrder == frontOrder) {
            return false;
        } else {
            return true;
        }
    }

    bool isOrderRangeSatisfactory(int i, int j, int k) {
        return i <= j + k && i >= j - k;
    }

    void sortNumbers(vector<int> &nums, vector<int> &order, int bottom, int top) {
        if (bottom >= top) return;
        int i = bottom, j = top;
        int saveValue = nums[i];
        int saveIndex = order[i];
        while (i < j) {
            for (; i < j && nums[j] >= saveValue; --j);
            nums[i] = nums[j];
            order[i] = order[j];
            for (; i < j && nums[i] <= saveValue; ++i);
            nums[j] = nums[i];
            order[j] = order[i];
        }
        nums[i] = saveValue;
        order[i] = saveIndex;
        sortNumbers(nums, order, bottom, i - 1);
        sortNumbers(nums, order, i + 1, top);
    }
};