0

我有一个问题，我分析并概括到这个级别，我需要解决这个问题以提高性能

我从数据库中收集了大量项目，如 1_A_B、2_A、2_B、2_A_C、1_C、1_B、2_B_C 等等。

现在当用户拿起A时（他只能拿起字母，基于该数值应该返回），他需要得到2，因为 2_A 存在，这意味着选择 A 时可以显示 2

如果用户拿起B，他将获得2,1，如果他拿起 B_C ，他将只获得2

输入顺序是随机的。那么我应该如何设计或设计哪种数据结构以获得最佳性能以保持最佳内存使用

我想用Map<Alphabets,List<Numerics>>字母组合来显示数字并不是一件容易的事[B_C 和 C_B 应该返回相同的结果，并且会有很多字母组合]

4

2 回答 2

2

我不知道这是否能很好地解决您的问题，但如果您的字母相当有限，我会解析每个字母并将其转换为 2 的幂。

例如，我分配

A = 1 (2^0)
B = 2 (2^1)
C = 4 (2^2)
D = 8 (2^3)

.. 等等。

然后，我会用它HashMap<Integer, List<Integer>>来存储数据。在 HashMap 中，key 是 Alphabet 的数值之和，value 变成了作为数据前缀的数字列表。

例如，给定1_A_B, 2_A, 2_B, 2_A_C, 1_C, 1_B, 2_B_C，

1_A_B 将存储在 map[3, {1}] 下，2_A 将存储在 map[1, {2}] 下，依此类推。因此，给定数据集的地图看起来像

3, {1} //1_A_B
1, {2} //2_A
2, {2, 1} //2_B , 1_B
5, {2} //2_A_C
4, {1} //1_C
6, {2} //2_B_C

当输入 B_C 时，您可以简单地查找值为 6 (B+C) 的键，从而返回 2 作为答案。

上述方法也适用于处理 B_C 和 C_B 的情况，因为 B_C 和 C_B 的总和相同。

于 2013-02-19T05:23:11.430 回答
1

我会用一个

HashMap<String,Integer>

，对于稀疏数据更好。在输入字符串之前，对其进行解析排序。这样 B_C 和 C_B 将被认为是相同的。
当您检查是否存在时，还要在检查之前进行解析和排序。

编辑：对于每个输入，您在哈希表中存储 1 个元素。例如：应输入3_C_A，拆分排序后为

<"AC",3>

要检查是否存在，例如“C”，您需要搜索哈希映射的键。

Pseudo-code
Foreach(key in hash.keys) {
    Print hash(key) if x found in key
}

内存使用：O(n)
搜索性能：O(n)

于 2013-02-19T05:06:10.473 回答