Leetcode0954. 二倍数对数组(medium)
目录
1. 题目描述
给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。
示例 1：
输入：arr = [3,1,3,6] 输出：false
示例 2：
输入：arr = [2,1,2,6] 输出：false
示例 3：
输入：arr = [4,-2,2,-4] 输出：true 解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
提示：
0 <= arr.length <= 3 * 10^4arr.length是偶数-10^5 <= arr[i] <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 方法一：暴力方法
2.1 思路
重组云云的操作都是幌子。实质上就是找满足len(arr)/2组满足a[j]=2a[i]的数对是否存在（每个数只能用一次）。
按索引从小到大遍历数组，如果对于a[i]找到a[j]=2a[i]，则认为找到一对，将该两个数排除，继续下一个数对的搜索。
但是，单纯的暴力方法对于本题来说却不一定可行。比如说，某个数组中包含有1,2,4,8这样4个数，1和2，4和8分别配对是可行的，但是如果是先针对2进行搜索，让2与4配对的话，就不可行了。也就是说跟搜索顺序还相关。
这个问题可以通过先对数组进行排序后解决。
还有另外一个问题，以上排序后处理成立基于一个前提，那就是对于每个数，与它配对的两倍数一定是排在它后面。但是输入数组的元素可能是负数。对于负数，这个前提就不成立了。对于这个问题的解决方案是，排序后，分非负数和负数进行分别考虑。对于非负数，找它的两倍数，对于负数，则找等于它的二分之一的数。
2.2 代码实现
class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
# First, sorting the input array
arr.sort()
# Brute-force search
while len(arr) > 0:
num = arr.pop(0)
pairFound = False
if num >= 0:
for j in range(0,len(arr)):
if arr[j] == 2*num:
arr.pop(j)
pairFound = True
break
if not pairFound:
return False
else:
for j in range(0,len(arr)):
if 2*arr[j] == num:
arr.pop(j)
pairFound = True
break
if not pairFound:
return False
return TrueUnsurprisingly, 提交超时。需要找到更好的办法。
3. 方法二
3.1 思路
在方法一的基础上做一些改进。
同样先对数组进行排序。
方法一在每找到一对数后从列表中删除，这个开销应该非常大。
对于排好序的数组来说，如果j > i，则与a[j]配对的数一定是排在a[i]配对数的后面。这样，可以不用进行从列表中删除的操作。而是随着搜索向后进行，不断地缩小搜索范围：如果对于a[i]的配对数的索引是k，则针对a[i+1]的搜索可以从k+1开始。
同理，不难证明，对于任意a[i]，与之配对的数的索引一定不会大于len(arr)/2+i。这样就进一步缩小了搜索范围。
但是，由于没有将配对的数从数组中排除，所以需要考虑避免重复搜索的问题，以输入arr = [4,-2,2,-4]为例，针对-4找到了-2与之配对后，后面就不能再针对-2进行搜索了。可以另外设置一个标志数组来解决这个问题。
3.2 代码实现
class Solution:
def canReorderDoubled2(self, arr: List[int]) -> bool:
if len(arr)%2 != 0:
return False
# First, sorting the input array
arr.sort()
# Brute-force search
flaged = len(arr) * [False]
nextStart = 0
for k in range(len(arr)):
if flaged[k]:
continue
num = arr[k]
pairFound = False
if num >= 0:
for j in range(nextStart,min(len(arr),len(arr)//2+k+1)):
if arr[j] == 2*num:
nextStart = j+1
pairFound = True
flaged[j] = True
break
if not pairFound:
return False
else:
for j in range(nextStart,min(len(arr),len(arr)//2+k+1)):
if 2*arr[j] == num:
nextStart = j+1
pairFound = True
flaged[j] = True
break
if not pairFound:
return False
return True
if __name__ == '__main__':
sln = Solution()
arr = []
print(sln.canReorderDoubled1(arr))
print(sln.canReorderDoubled2(arr))
arr = [3,1,3,6]
print(sln.canReorderDoubled1(arr))
print(sln.canReorderDoubled2(arr))执行用时：216 ms, 在所有 Python3 提交中击败了51.75%的用户
内存消耗：16.9 MB, 在所有 Python3 提交中击败了67.13%的用户
回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)