LeetCode #1385 Find the Distance Value Between Two Arrays

問題概要

入力値：arr1(int aray), arr2(int array), d(int)
出力値：int

問題のリンク

入力例

arr1: [4,5,8]
arr2: [10,9,1,8]
d:2
result: 2

解答例1

計算量：O(n*m)
Brute force
Python

class Solution(object):
    def findTheDistanceValue(self, arr1, arr2, d):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :type d: int
        :rtype: int
        """
        result = 0
        for num1 in arr1:
            is_included = False
            for num2 in arr2:
                diff = abs(num1 - num2)
                if diff <= d:
                    is_included = True
                    break
            if not is_included:
                result += 1
        return result

Runtime: 65ms
Beats: 68.35%

C++

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int result = 0;
        for (int num1 : arr1) {
            bool is_included = false;
            for (int num2 : arr2) {
                int diff = abs(num1 - num2);
                if (diff <= d) {
                    is_included = true;
                    break;
                }
            }
            if (!is_included) {
                result += 1;
            }
        }
        return result;
    }
};

Runtime: 7ms
Beats: 65.79%

解答例2

Binary search
計算量:nlogm

Python

class Solution(object):
    def findTheDistanceValue(self, arr1, arr2, d):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :type d: int
        :rtype: int
        """
        arr2_length = len(arr2)
        arr2.sort()
        result = 0

        for num in arr1:
            left, right = 0, arr2_length - 1
            while left <= right:
                mid = (left + right) // 2
                if abs(num - arr2[mid]) <= d:
                    break
                elif num < arr2[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                result += 1
        return result

Runtime: 53ms
Beats: 89.24%

C++

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(begin(arr2), end(arr2));
        int arr2_length = arr2.size();
        int result = 0;
        for (int num : arr1) {
            int left = 0;
            int right = arr2_length - 1;
            bool is_valid = false;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (abs(num - arr2[mid]) <= d) {
                    is_valid = true;
                    break;
                } else if (num < arr2[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            if (!is_valid) {
                result += 1;
            }
        }
        return result;
    }
};

Runtime: 6ms
Beats: 72.69%