gpt4 book ai didi

algorithm - 保持最小值在线的数据结构

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:24:18 33 4
gpt4 key购买 nike

假设,我们有一串字符(假设它们的值在 0--255 范围内,对于 ASCII0- -65,535).

以下是可能应用的任务列表:

  1. 持续跟踪每个唯一字符的索引(最新的);
  2. 获取index最小的字符;
  3. 更新数据结构(删除 2 中返回的一个并添加一个新的)。

这是一个例子,索引i0到17

aabbaaaacccddccccc

我们可以这样在线跟踪字符串,其中括号内的整数是对应字符的索引:

  • 一个(0)
  • a(1) b(2)
  • a(1) b(3)
  • ...
  • a(7) b(3)
  • a(7) b(3) c(8)
  • ...
  • a(7) b(3) c(10)现在我们读取字符 'd' 并且我们需要用规则更新数据结构,比如说,删除具有最小索引的元素:b(3) 并添加 d(11)
  • a(7) d(11) c(10)
  • ...

我们可以使用 HashMap 来跟踪每个唯一字符的索引:

Map<Character, Integer> myMap = new HashMap<>(m);
myMap.put(new Character(input.charAt(j)), j);

但是当我们想要获取索引最小的字符时,我们可能会一个一个地遍历 map ,这并没有我想要的那么高效。

我们可以使用优先级队列来存储元素,这确实给了我 O(1) 的时间来获取最小的元素;但我无法像 map 一样更新优先级队列。

有什么想法吗?

最佳答案

除了将 myMap 从字符映射到位置之外,您还可以将 SortedMap 从位置更新到字符。

对于每个字符 c 输入,您将:

  1. 在 myMap 中查找 c 以找到它的索引 i
  2. 如果存在,则从 SortedMap 中删除键 i
  3. 更改 myMap[c] 以指向新索引
  4. 改变 SortedMap[new index] 指向 c

当你想找到索引最小的元素时,你可以简单地查看SortedMap的第一个元素。使用 SortedMap,这是一种高效的操作。

关于algorithm - 保持最小值在线的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21244065/

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