首页 > 其他 > 详细

[LeetCode]Contains Duplicate III

时间:2015-08-29 00:40:17      阅读:160      评论:0      收藏:0      [点我收藏+]

Contains Duplicate III

 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.

 

O(nk)时间复杂度的时间超限,无语,参考这个的,用的set。其实应该用二叉搜索树的。等看了再写吧。

 1 class Solution {
 2 public:
 3     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
 4     set<int> window;
 5     for (int i = 0; i < nums.size(); i++) 
 6     {
 7         if (i > k) window.erase(nums[i-k-1]);
 8         auto pos = window.lower_bound(nums[i] - t);
 9         if (pos != window.end() && *pos - nums[i] <= t)
10                return true;
11         window.insert(nums[i]);
12     }
13     return false;
14 }
15 };

 

[LeetCode]Contains Duplicate III

原文:http://www.cnblogs.com/Sean-le/p/4768115.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!