Skip to content

Latest commit

 

History

History
395 lines (341 loc) · 8.89 KB

README.md

File metadata and controls

395 lines (341 loc) · 8.89 KB
Raw

1346. 检查整数及其两倍数是否存在

English Version

题目描述

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

更正式地，检查是否存在两个下标 i 和 j 满足：

  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]

 

示例 1：

输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。

示例 2：

输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。

示例 3：

输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。

 

提示：

  • 2 <= arr.length <= 500
  • -10^3 <= arr[i] <= 10^3

解法

方法一：哈希表

使用哈希表 m 记录 arr 每个元素 v 及其对应的下标 i。

遍历 arr 每个元素 v，若能在哈希表中找到 v * 2，且下标值与当前 v 的下标值不相等，说明找到了满足条件的元素，返回 true。否则遍历结束返回 false。

时间复杂度：$O(n)$。 空间复杂度：$O(n)$。

方法二：排序 + 二分查找

首先对 arr 排序。

然后遍历 arr 每个元素 v，二分查找 arr 中是否存在 v * 2 元素，是则返回 true。

注意，元素可能为 0，这种情况下，v*2 的值同样为 0，二分查找可能会找到同个位置的元素，与题意不符。因此，可以预先统计 arr 中元素 0 的个数，若超过 1 个，可提前返回 true。

Python3

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        m = {v: i for i, v in enumerate(arr)}
        return any(v << 1 in m and m[v << 1] != i for i, v in enumerate(arr))
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        if arr.count(0) > 1:
            return True
        arr.sort()
        n = len(arr)
        for v in arr:
            idx = bisect_left(arr, v * 2)
            if v != 0 and idx != n and arr[idx] == v * 2:
                return True
        return False

Java

class Solution {
    public boolean checkIfExist(int[] arr) {
        Map<Integer, Integer> m = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            m.put(arr[i], i);
        }
        for (int i = 0; i < n; ++i) {
            if (m.containsKey(arr[i] << 1) && m.get(arr[i] << 1) != i) {
                return true;
            }
        }
        return false;
    }
}
class Solution {
    public boolean checkIfExist(int[] arr) {
        int cnt = 0;
        for (int v : arr) {
            if (v == 0) {
                ++cnt;
                if (cnt > 1) {
                    return true;
                }
            }
        }
        Arrays.sort(arr);
        for (int v : arr) {
            if (v != 0) {
                int idx = Arrays.binarySearch(arr, v * 2);
                if (idx >= 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

TypeScript

function checkIfExist(arr: number[]): boolean {
    const s = new Set();
    for (const v of arr) {
        if (s.has(v << 1) || s.has(v / 2)) {
            return true;
        }
        s.add(v);
    }
    return false;
}
function checkIfExist(arr: number[]): boolean {
    let cnt = 0;
    for (const v of arr) {
        if (v == 0) {
            ++cnt;
            if (cnt > 1) {
                return true;
            }
        }
    }
    const n = arr.length;
    arr.sort((a, b) => a - b);
    for (const v of arr) {
        if (v != 0) {
            let left = 0,
                right = n;
            while (left < right) {
                const mid = (left + right) >> 1;
                if (arr[mid] >= v * 2) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (left != n && arr[left] == v * 2) {
                return true;
            }
        }
    }
    return false;
}

C++

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_map<int, int> m;
        int n = arr.size();
        for (int i = 0; i < n; ++i) m[arr[i]] = i;
        for (int i = 0; i < n; ++i)
            if (m.count(arr[i] * 2) && m[arr[i] * 2] != i)
                return true;
        return false;
    }
};
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        int cnt = 0;
        for (int& v : arr) if (v == 0) ++cnt;
        if (cnt > 1) return true;
        sort(arr.begin(), arr.end());
        int n = arr.size();
        for (int& v : arr)
        {
            if (v == 0) continue;
            int idx = lower_bound(arr.begin(), arr.end(), v * 2) - arr.begin();
            if (idx != n && arr[idx] == v * 2) return true;
        }
        return false;
    }
};

JavaScript

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var checkIfExist = function (arr) {
    const s = new Set();
    for (const v of arr) {
        if (s.has(v << 1) || s.has(v / 2)) {
            return true;
        }
        s.add(v);
    }
    return false;
};
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var checkIfExist = function (arr) {
    let cnt = 0;
    for (const v of arr) {
        if (v == 0) {
            ++cnt;
            if (cnt > 1) {
                return true;
            }
        }
    }
    const n = arr.length;
    arr.sort((a, b) => a - b);
    for (const v of arr) {
        if (v != 0) {
            let left = 0,
                right = n;
            while (left < right) {
                const mid = (left + right) >> 1;
                if (arr[mid] >= v * 2) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (left != n && arr[left] == v * 2) {
                return true;
            }
        }
    }
    return false;
};

Go

func checkIfExist(arr []int) bool {
	m := make(map[int]int)
	for i, v := range arr {
		m[v] = i
	}
	for i, v := range arr {
		if j, ok := m[v*2]; ok && j != i {
			return true
		}
	}
	return false
}
func checkIfExist(arr []int) bool {
	cnt := 0
	for _, v := range arr {
		if v == 0 {
			cnt++
			if cnt > 1 {
				return true
			}
		}
	}
	sort.Ints(arr)
	n := len(arr)
	for _, v := range arr {
		if v != 0 {
			left, right := 0, n
			for left < right {
				mid := (left + right) >> 1
				if arr[mid] >= v*2 {
					right = mid
				} else {
					left = mid + 1
				}
			}
			if right != n && arr[left] == v*2 {
				return true
			}
		}
	}
	return false
}

Rust

use std::collections::HashMap;
impl Solution {
    pub fn check_if_exist(arr: Vec<i32>) -> bool {
        let mut map = HashMap::new();
        for (i, v) in arr.iter().enumerate() {
            map.insert(v, i);
        }
        for (i, v) in arr.iter().enumerate() {
            if map.contains_key(&(v * 2)) && map[&(v * 2)] != i {
                return true;
            }
        }
        false
    }
}
use std::cmp::Ordering;
impl Solution {
    pub fn check_if_exist(mut arr: Vec<i32>) -> bool {
        arr.sort();
        let n = arr.len();
        for i in 0..n {
            let target = arr[i] * 2;
            let mut left = 0;
            let mut right = n;
            while left < right {
                let mid = left + (right - left) / 2;
                match arr[mid].cmp(&target) {
                    Ordering::Less => left = mid + 1,
                    Ordering::Greater => right = mid,
                    Ordering::Equal => {
                        if mid == i {
                            break;
                        }
                        return true;
                    }
                }
            }
        }
        false
    }
}

...