gpt4 book ai didi

arrays - 检测序列的排列

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:06:36 25 4
gpt4 key购买 nike

我有一个这样的数字列表(数组)

1 2 3 4

所以我的目标是检查给定的另一个数组,如果这个数组是原始示例的排列,数组 (3 4 1 2)(1 2 4 3) 是原始排列,但 (1 2 1 1)(1 5 4 3) 不是。

最佳答案

两种可能的解决方案是:

(1) O(n) 空间和平均时间解决方案将创建一个 histogram ,基于数据的哈希表 - 并检查直方图是否相同。这个想法是 - 计算每个元素在每个列表中出现的次数,然后检查每个元素在每个数组中完全出现的次数。

伪代码:

map1 = new map //first histogram
map2 = new map //second histogram
for each element in arr1: //create first histogram
if (element in map1):
map1.put(element,map1.get(element)+1)
else:
map1.put(element,1)
for each element in arr2: //create second histogram
if (element in map2):
map2.put(element,map2.get(element)+1)
else:
map2.put(element,1)
for each key in map 1: //check all elements in arr1 appear in arr2
if map1.get(key) != map2.get(key):
return false
//make sure the sizes also match, it means that each element in arr2 appears in arr1.
return arr1.length == arr2.length

(2) O(nlogn) 时间解决方案是对两个数组进行排序,然后迭代并检查它们是否相同。

关于arrays - 检测序列的排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12257735/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com