[数据结构与算法] LeetCode 1346. 检查整数及其两倍数是否存在

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode 1346. 检查整数及其两倍数是否存在 -> 正文阅读

[数据结构与算法]LeetCode 1346. 检查整数及其两倍数是否存在

题目链接：

力扣https://leetcode.cn/problems/check-if-n-and-its-double-exist/

【方法一二分查找】需要注意0的情况，所以二分查找要查找到下标，然后进行二次判断

class Solution {

    public int binarySearch(int[] arr, int target){
        int left = 0, right = arr.length - 1, mid;
        while(left <= right){
            mid = (left + right) >>> 1;
            if(arr[mid] == target) return mid;
            else if(arr[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return left == arr.length? right: left;
    }

    public boolean checkIfExist(int[] arr) {
        Arrays.sort(arr);
        int idx, n = arr.length;
        for(var i = 0; i < n; i++){
            idx = binarySearch(arr, arr[i] * 2);
            if(idx != i && arr[idx] == arr[i] * 2) return true;
        }
        return false;
    }
}

【方法二哈希表】用HashMap来记录出现次数。

class Solution {
    public boolean checkIfExist(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap();
        for(var i: arr){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for(var i: arr){
            if(i == 0){
                if(map.getOrDefault(0, 0) > 1) return true;
            }else{
                if(map.getOrDefault(i * 2, 0) > 0) return true;
            }
        }
        return false;
    }
}