程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Leetcode 220 Contains Duplicate III

Leetcode 220 Contains Duplicate III

編輯:關於C++

1. 問題描述

  給定一個整數數組nums[],查找是否存在兩個下標i和j,滿足|numsi?numsj|≤t|i?j|≤k


2. 方法與思路

  總得思路就是:“滑動窗口”+unordered_map。
  推理過程如下:
  |numsi?numsj|≤t?|numsi/t?numsj/t|≤1
  由上式可以推出:|?numsi/t???numsj/t?|≤1
  等價於:?numsi/t?∈{?numsj/t?,?numsj/t??1,?numsj/t?+1}
  我們只需要維持一個大小為K的窗口,鍵值為?numsi/t?, 值為numsi。然後循環遍歷nums[]數組,與unordered_ map中鍵集對應的值進行差得絕對值運算,再判斷即可。
  對於STL中關於unordered_map的相關可參考官方References 對unordered_map講解。

注意: unordered_map是一種特殊的hash map,它不按照鍵值進行排序。通過hash表的算法,查找效率為O(1)。但會消耗一定內存。進行差值運算時需轉換為long類型,否則會溢出。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
        if(t < 0 | k <1)
            return false;

        int i,key;
        unordered_map dict;

        for(i =0; i < nums.size(); i++)
        {
            key = nums[i]/max(1,t);
            //map::iterator it;
            if( (dict.find(key) != dict.end() && abs(nums[i] - dict[key]) <= t) ||
                (dict.find(key-1) != dict.end() && abs((long)nums[i] - (long)dict[key-1]) <= t) ||
                (dict.find(key+1) !=dict.end() && abs(nums[i] - dict[key+1]) <= t))
            {                           
                return true;
            }

            //dict[key] = nums[i];
            dict.insert(pair(key,nums[i]));

            if(i >= k)
            {   
                dict.erase(nums[i-k]/max(1,t)); //刪除窗口大小之外的鍵值
            }

        }
        return false;       
    }
};
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved