将数组用作字典键是否属于不良编程实践?
用字符串作为字典键解决数组去重问题(以LeetCode 3Sum/4Sum为例)
在Python中,数组无法直接作为字典的键,但可以将数组转换为逗号分隔的字符串来充当字典键。我在LeetCode的3Sum、4Sum等问题中使用过这个方法,均能通过测试。具体步骤如下:
- 排序数组
- 将数组转换为字符串
- 存入字典
- 以O(1)的时间复杂度检查重复项
以下是用这个方法实现的3Sum完整解决方案:
class Solution(object): def threeSum(self, nums): finreturn = [] count_dict = {} # 统计每个数字的出现次数 for num in nums: if num in count_dict: count_dict[num] += 1 else: count_dict[num] = 1 comparedict = {} for key1 in count_dict: for key2 in count_dict: target = -(key1 + key2) if target in count_dict: # 临时减少计数,避免重复使用同一元素 count_dict[key1] -= 1 count_dict[key2] -= 1 count_dict[target] -= 1 # 生成三元组并排序 temp_list = [key1, key2, target] temp_list.sort() # 转换为字符串作为去重判断的键 compare_key = f"{temp_list[0]},{temp_list[1]},{temp_list[2]}" # 检查计数合法且该三元组未被记录过 if count_dict[key1] >= 0 and count_dict[key2] >= 0 and count_dict[target] >= 0 and compare_key not in comparedict: finreturn.append(temp_list) comparedict[compare_key] = 1 # 恢复计数,不影响后续循环 count_dict[key1] += 1 count_dict[key2] += 1 count_dict[target] += 1 return finreturn
内容的提问来源于stack exchange,提问作者Matthew Setiawan
相关产品推荐
相关产品推荐

