Chứa bản sao III trong C ++

Giả sử chúng ta có một mảng các số nguyên, chúng ta phải kiểm tra xem có hai chỉ số i và j khác nhau trong mảng sao cho sự khác biệt tuyệt đối giữa nums [i] và nums [j] tối đa là t. Và sự khác biệt tuyệt đối giữa i và j nhiều nhất là k. Vì vậy, nếu đầu vào giống như [1,2,3,1], thì nếu k =3 và t =0, thì trả về true.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một tập hợp s, n:=kích thước của mảng nums

• cho tôi trong phạm vi từ 0 đến n - 1

  • x là chỉ số của phần tử tập hợp bắt đầu từ nums [i] trở lên

  • nếu x không nằm trong phạm vi của tập hợp và giá trị của x <=nums [i] + t, thì trả về true

  • nếu x không phải là phần tử đầu tiên

    • x:=phần tử tiếp theo là ngẫu nhiên

    • nếu phần tử thứ t bắt đầu từ x là> =nums [i], thì trả về true

  • chèn nums [i] vào s, sau đó xóa nums [i - k] khỏi s

• trả về false

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
      multiset <int> s;
      int n = nums.size();
      for(int i = 0; i< n; i++){
         multiset <int> :: iterator x = s.lower_bound(nums[i]);
         if(x != s.end() && *x <= nums[i] + t ) return true;
            if(x != s.begin()){
               x = std::next(x, -1);
               if(*x + t >= nums[i])return true;
            }
            s.insert(nums[i]);
            if(i >= k){
               s.erase(nums[i - k]);
            }
         }
         return false;
      }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,1};
   cout << (ob.containsNearbyAlmostDuplicate(v, 3,0));
}

Đầu vào

[1,2,3,1]
3
0

Đầu ra

1