当前位置：网站首页>LeetCode 1346、检查整数及其两倍数是否存在

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

2022-04-23 20:23:00 【亡于灬】

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

1）题目描述

给你一个整数数组 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

2）分析

排序，二分查找。

  • 先对数组进行排序；
  • 再通过二分查找数组中是否存在等于当前元素二倍的元素，在二分查找中，为了避免0导致出错，要排除当前元素本身。

3）C++代码

class Solution {
    
public:
    bool checkIfExist(vector<int>& arr) {
    
        sort(arr.begin(),arr.end());
        for(int i=0;i<arr.size();i++){
    
            int left=0;
            int right=arr.size()-1;
            while(left<=right){
    
                int mid=(left+right)/2;
                if(arr[mid]==2*arr[i]&&i!=mid)
                    return true;
                else if(arr[mid]<2*arr[i])
                    left=mid+1;
                else
                    right=mid-1;
            }
        }
        return false;
    }
};

版权声明
本文为[亡于灬]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_38342510/article/details/124360356

边栏推荐

猜你喜欢

随机推荐