[leetcode] 1346. Check If N and Its Double Exist

[leetcode] 1346. Check If N and Its Double Exist

Description

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that :

i != j0 <= i, j < arr.lengtharr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]Output: trueExplanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2:

Input: arr = [7,1,14,11]Output: trueExplanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3:

Input: arr = [3,1,7,11]Output: falseExplanation: In this case does not exist N and M, such that N = 2 * M.

Constraints:

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

分析

题目的意思是：给你一个数组，问是否存在一个数是另一个数的2倍，我的想法是先根据绝对值排序，因为有负数，然后再遍历判断当前的数是否在以下一个数为开始的数组里面，如果能够找到说明存在，这个解法的时间复杂度为O(nlogn)，全都花在排序上面了，我看了一下别人O(n)的解法，是考虑了正数和负数两种情况，把遍历过的数加入到集合里面，如果一个数的1/2正好在这个集合里面，说明存在啦，构思还挺巧妙的。

代码

class Solution: def checkIfExist(self, arr: List[int]) -> bool: arr=sorted(arr,key=lambda x:abs(x)) n=len(arr) j=n-1 i=0 for i in range(n): if(arr[i]*2 in arr[i+1:]): return True return False

参考文献

​​[LeetCode] Python O(N) solution​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。