leetcode 1385. Find the Distance Value Between Two Arrays

问题来自 leetcode 1385. Find the Distance Value Between Two Arrays

---

naive的做法就是两层for loop，本来以为会超时，结果居然过了

---

1, 两层for loop

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int size1 = arr1.size();
        int size2 = arr2.size();
        
        int result = 0;
        for (int i = 0; i < size1; ++i) {
            bool valid = true;
            for (int j = 0; j < size2; ++j) {
                if (abs(arr1[i]-arr2[j]) <= d) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                ++result;
            }
        }
        
        return result;
    }
};

---

2, sort

下面的代码时间复杂度是O(nlogn)，但是居然比上面的O(n^2)运行还要慢。。。。

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());

        int size1 = arr1.size();
        int size2 = arr2.size();

        int result = 0;
        for (int i = 0; i < size1; ++i) { 
            int index = binarySearch(arr2, arr1[i]); 
            bool valid = true; 
            if (index >= 0 && index < size2) {
                if (abs(arr1[i] - arr2[index]) <= d) { 
                    valid = false; 
                } 
            } 
            index++; // check the next element 
            if (index >= 0 && index < size2) {
                if (abs(arr1[i] - arr2[index]) <= d) {
                    valid = false;
                }
            }
            if (valid) {
                ++result;
            }
        }

        return result;
    }

    // Return the index, which either sorted[index] == target or
    // sorted[index] < target && index is the nearest to target
    int binarySearch(vector &sorted, int target) {
        int low = 0;
        int high = sorted.size() - 1;
        while(low <= high) {
            int mid = (low + high) / 2;
            if (sorted[mid] == target) {
                return mid;
            } else if (sorted[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return high;
    }
};