JZX轻语：简
LeetCode 2007 - 从双倍数组中还原数组
发表于2024年04月18日
数组题，朴素的想法是遍历数组，对于数字i寻找是否有i // 2或者i * 2，但这样子如果都存在上述两种可能，则无法确定用哪个（如果用i // 2，则可能会存在i // 2 // 2找不到匹配的情况，而这个数是用来匹配i * 2的）。因此，需要使用贪心的办法，从小到大寻找双倍匹配，如果其中有个数无法找到双倍匹配，则直接返回空数组。
有两种做法：一种基于哈希表，另一种则基于双指针查找。
哈希表版本，需要特殊处理值为0的情况：
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
if len(changed) % 2:
return []
cnt = {}
for num in changed:
cnt[num] = cnt.get(num, 0) + 1
ans = []
# 从小到大寻找匹配
# 小的数字要全部用完
for num in sorted(cnt.keys()):
if cnt[num] == 0: # 已经用完了
continue
c = cnt[num] # 该数字的计数
if num == 0:
c //= 2
if cnt.get(2 * num, 0) < c: # 双倍数不够用了
return []
cnt[2 * num] -= c # 使用掉对应数量的双倍数
ans += [num] * c
return ans使用双指针的方法，使用一个visited数组标记这个数字是否被使用了，指针i用于指向原来的数，j用于指向二倍数：
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
if len(changed) % 2:
return []
changed.sort()
visited = [False] * len(changed)
i, j = 0, 1
result = []
while i < len(changed):
if not visited[i]:
visited[i] = True
double = changed[i] * 2
while j < len(changed):
# 找到第一个大于等于double、未被访问的数字
if not visited[j] and changed[j] >= double:
break
j += 1
# 找不到相应的匹配, 返回空数组
if j == len(changed) or changed[j] > double:
return []
visited[j] = True
result.append(changed[i])
i += 1
return result