leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0719.cpp (715B)

0 class Solution { 1 int count(const vector<int> &nums, int tgt) const { 2 int res = 0; 3 4 for (int l = 0, r = 1; r < size(nums); r++) { 5 while (nums[r] - nums[l] > tgt) 6 l++; 7 res += r - l; 8 } 9 10 return res; 11 } 12 13 public: 14 int smallestDistancePair(vector<int> &nums, int k) const { 15 sort(begin(nums), end(nums)); 16 17 int low = 0, high = nums.back() - nums.front(); 18 while (low < high) { 19 const int mid = low + (high - low) / 2; 20 const int cnt = count(nums, mid); 21 22 if (cnt < k) 23 low = mid + 1; 24 else 25 high = mid; 26 } 27 28 return low; 29 } 30 };