检查N及其双重存在的Leetcode解决方案


难度级别 易得奖学金
经常问 谷歌
排列

问题陈述

在“检查N是否存在并且其双精度存在”问题中,我们得到了n个元素的数组。 数组长度大于或等于XNUMX。

我们的任务是检查数组中是否存在一对,使得第一个值是第二个值的两倍。

更正式地说,我们需要检查是否存在i,j

使用案列

arr = [7,1,14,11]
true

说明:

检查N及其双重存在的Leetcode解决方案

此输入的输出为true,因为问题要求我们检查给定数组中是否有任何值及其双精度出口,因此7和14满足这些条件,因为14是7的两倍。

检查N及其双重存在的Leetcode解决方案的方法

解决此问题的第一种方法是 蛮力 方法。 对于数组中的每个元素,我们将遍历完整的数组并检查其是否存在两倍。 如果找到满足此条件的元素,则将返回true,否则,最后将返回false。 这种方法的时间复杂度为O(n * n),因为对于数组的每个元素,我们都遍历整个数组。

我们可以使用无序映射或无序集合以更好的时间复杂度解决此问题。

  1. 遍历数组。
  2. 对于数组中的每个元素,检查它是否为两倍或一半是否已存在于映射中。
  3. 如果条件为true,则简单地返回true,否则将该元素添加到地图中。
  4. 如果完成数组遍历,但没有找到任何元素的两倍,则返回false。

实施

用于检查N是否存在且其双重存在的C ++代码

#include <bits/stdc++.h> 
using namespace std; 
    bool checkIfExist(vector<int>& arr) {
      unordered_map<int,bool>mp;
        for(int i=0;i<arr.size();i++)
        {
            if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
                return true;
            mp[arr[i]]=1;
        }
        return false;
    }
int main() 
{ 
 vector<int> arr = {7,1,14,11}; 
 bool ans=checkIfExist(arr);
 cout <<boolalpha;
 cout<<ans<<endl;
 return 0;
}
true

用于检查N是否存在及其双重存在的Java代码

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();   
        for (int i : arr) {
            if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
                return true;
            seen.add(i);
        }
        return false;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,14,11}; 
        boolean ans=checkIfExist(arr); 
        System.out.println(ans);
  }
}
true

Check if N及其双重存在的Leetcode解的复杂性分析

时间复杂度

上面代码的时间复杂度是 O(N) 考虑在无序映射中搜索和插入的平均时间复杂度为O(1)。

空间复杂度

上面代码的空间复杂度是 O(N) 因为在最坏的情况下,我们可能需要存储所有元素。

參考資料