题目：

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

解答：

首先这题用例挺TM蠢的，题目说了t和k为绝对值，居然还有k为负数的用例，劳资又不是ACM选手，只是想刷个算法题而已。。

1.桶排序:

照着官方题解写的。不过有几个用例过不去，如t==0的特殊情况，利用len(list)!=len(set(list))可判断，还有t<0、k<0的（sb）用例额外判断一下，以及某些极其分散的用例，如[200000000000,-2222222222222222],2,2这样的。我是判断一下llog(l)和max-min的大小关系（l是数组长度，max、min分别为数组最大最小数），若llogl小，那就直接排序解决，不然用桶排序的话要生成的桶太多了，而且几乎全部是无用的桶。

复杂度O(n)

代码：

 from math import log

 class Solution:

     def containsNearbyAlmostDuplicate(self, nums, k, t) :

         l=len(nums)

         if l< or t< or k<:

             return False

         if (t==):

             return len(nums)!=len(set(nums))

         _max=max(nums)

         _min=min(nums)

         if l*log(l)<_max-_min:

             for i in range(l):

                 for j in range(max(i-k,),i):

                     if abs(nums[i]-nums[j])<=t:

                         return True

             return False

         hashtable=[[]for i in range((_max-_min)//t+1)]

         for i in range(l):

             x=nums[i]

             m=(x-_min)//t

             for p in hashtable[m]:

                 if abs(p[]-i)<=k and abs(p[]-x)<=t:

                     return True

             le,ri=m-,m+

             if le>=:

                 for y in hashtable[le]:

                     if abs(y[]-i)<=k and abs(y[]-x)<=t:

                         return True

             if ri<len(hashtable):

                 for z in hashtable[ri]:

                     if abs(z[]-i)<=k and abs(z[]-x)<=t:

                         return True

             hashtable[m].append((i,x))

         return False

2.二叉搜索树+滑动窗口:

由于对于两个数的索引差有绝对值<=k的限制，所以考虑维护一个长度k的窗口进行滑动。但由于窗口内的元素是无序的，如果对于每个窗口我们都进行排序，复杂度会太高。所以考虑用有序集合（C++里的set或者multi_set），窗口大小k由我们自己维护，窗口内的有序性交给set进行维护。每当我们滑动窗口时，考察右边移入窗口的新数字nums[i]，因为窗口内的数字和当前索引i的索引差的绝对值一定满足<=k的要求，那么如果窗口内有相同的数字就可以返回true。如果没有，查找窗口内有无满足大小介于[nums[i]-t,nums[i]+t]范围内的数字，如果有则返回true。这里利用C++的lower_bound和upper_bound函数。

map/set.lower_bound(num)，返回大于等于num的第一个迭代器

map/set.upper_bound(num)，返回大于num的第一个迭代器

带模板的lower_bound格式是这样的：lower_bound<容器迭代器类型，容器元素类型>(起始迭代器，尾迭代器，元素)，如：

lower_bound<vector<int>::iterator,int>(p.begin(),p.end(),);

upper_bound模板函数类似。

这个方法还是挺巧妙的，以前没有见过，记录下，滑动窗口不一定专属于线性结构。

复杂度：O(n logk)

代码：

比较坑爹的是有几个大数用例，得加long，不然AC不了。

 class Solution {

 public:

     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

         if(t< or k<){return false;}

         set<long> st;

         for (int i = ; i < nums.size(); ++i) {

             if (st.count(nums[i])) {

                 return true;

             }

             auto it = st.upper_bound(nums[i]);

             if (it != st.end() and *it - nums[i] <= t) {

                 return true;

             }

             it = st.lower_bound(long(nums[i]) - t);

             if (it != st.end() and *it<nums[i]) {

                 return true;

             }

             st.insert(nums[i]);

             if (st.size() == k+) {

                 st.erase(nums[i-k]);

             }

         }

         return false;

     }

 };

2020-02-17 15:30:19

巴特西

220. 存在重复元素 III

题目：

解答：

1.桶排序:

代码：

2.二叉搜索树+滑动窗口:

代码：

最新文章

热门文章