leetcode 220. 存在重复元素 III

leetcode 220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。

找出满足下述条件的下标对 (i, j)：

• i != j,
• abs(i - j) <= indexDiff
• abs(nums[i] - nums[j]) <= valueDiff

如果存在，返回 true *；*否则，返回 false 。

提示：

• 2 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 1 <= indexDiff <= nums.length
• 0 <= valueDiff <= 109

分析

由题意知，在区域下标内查找是否存在两个值，该两个值的差小于某一阈值

遇到绝对值先化简

abs(nums[i]-nums[j]) <= valueDiff
-valueDiff <= nums[i] - nums[j] <= valueDiff
-valueDiff - nums[i] <= -nums[j] <= valueDiff - nums[i]
-valueDiff + nums[i] <= nums[j] <= valueDiff + nums[i]

转变为查找在区域内是否存在一个值属于[-valueDiff + nums[i],valueDiff + nums[i]]

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        multiset<long long> set;  
        for(int i = 0; i < nums.size(); ++i) {
            if(i > indexDiff) { //维持窗口大小为k(indexDiff)
                //set.erase(nums[i-indexDiff-1])//multiset指定元素删除，会删掉所有这个值的元素
                set.erase(set.find(nums[i-indexDiff-1]));//find()返回的是查找到的第一个元素位置的迭代器
            }
            /*
            遇到绝对值先化简
            abs(nums[i]-nums[j]) <= valueDiff
            -valueDiff <= nums[i] - nums[j] <= valueDiff
            -valueDiff - nums[i] <= -nums[j] <= valueDiff - nums[i]
            -valueDiff + nums[i] <= nums[j] <= valueDiff + nums[i]
            */
            auto leftBound = set.lower_bound(nums[i] - (long long)valueDiff);// multiset是有序的，可以使用二分查找查询边界
            auto rightBound = set.upper_bound(valueDiff + (long long)nums[i]);//实际上返回的是第1个大于valueDiff + (long long)nums[i]的元素的位置
            if(leftBound != rightBound) {	//若存在则至少有一个，所以
                return true;
            }
            set.insert(nums[i]);//前面的元素不满足条件，那么察看下一个位置的元素
        } 
        return false;
    }
};

lower_bound( )和upper_bound( )

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在中，

• lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

• upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在，重载lower_bound()和upper_bound()

• lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

• upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

  #include<bits/stdc++.h>
  using namespace std;
  const int maxn=100000+10;
  const int INF=2*int(1e9)+10;
  #define LL long long
  int cmd(int a,int b){
  	return a>b;
  }
  int main(){
  	int num[6]={1,2,4,7,15,34}; 
  	sort(num,num+6);                           //按从小到大排序 
  	int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
  	int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
  	cout<<pos1<<" "<<num[pos1]<<endl;
  	cout<<pos2<<" "<<num[pos2]<<endl;
  	sort(num,num+6,cmd);                      //按从大到小排序
  	int pos3=lower_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
  	int pos4=upper_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
  	cout<<pos3<<" "<<num[pos3]<<endl;
  	cout<<pos4<<" "<<num[pos4]<<endl;
  	return 0;	
  }