arrays - 搜索和更新数组整数值的最佳数据结构是什么？

Question

如果我的数组为 [7, 11, 13, 9, 4, 6]，并且用户输入为 10
，我想要刚好高于（或等于）10（在本例中为 11）的整数并将其替换为整数 - 10 (11 - 10)
我不能对列表和二分搜索进行排序，因为我必须返回更新元素的索引。
我研究了对（索引，整数）对进行排序，然后进行二进制搜索，但是在更新之后，我必须重新排序对数组以供下一个用户输入。

原始数组 = [7, 11, 13, 9, 4, 6]
排序数组 = [4, 6, 7, 9, 11, 13]
用户输入 = 10
输出 = 1（更新整数的索引）

更新排序数组 = [4, 6, 7, 9, 1, 13]
重新排序数组 = [1, 4, 6, 7, 9, 13]
用户输入 = 4
...

什么数据结构适合实现这个?

标签： arraysdata-structureshashmapbinary-searchavl-tree

Answer 1

您可以使用有序集来存储 (value, index) 元组。您可以定义自定义比较函数来满足您的目标（这取决于所讨论的编程语言）。

有序集操作包括：

1. 添加一个元素。
2. 移除一个元素。
3. 搜索一个元素。
4. 搜索大于或等于给定元素的元素。
5. 搜索大于给定元素的元素。

可以使用具有上述操作的有序集来解决给定的问题。

一些编程语言（如c++ 中的set）具有预定义的数据结构，因此您无需从头开始实现它（仅用于使用它）。有序集内部实现通常是Red-Black Tree (c++) 或AVL Tree。

检查您的编程语言是否具有内置的有序集或使用包含它的某些库。这是一个非常有用且通用的数据结构，因此不难找到。