c ++将大数字字符串映射到数字字符串范围

Question

我必须编写一个 C++ 函数，其中输入是一个 12 位数字字符串。我必须找到也存储在字符串数组中的范围。

例如，

范围数组 [10]:
1 - 111115555522 - 111225555521
2 - 111225555522 - 111335555521
3 - 111335555522 - 111445555521
4 - 111445555522 - 111555555521
5 - 111555555522 - 111665555521
6 - 111665555522 - 111775555521
7 - 111775555522 - 111885555521
8 - 111885555522 - 111995555521
9 - 111995555522 - 112005555521
10- 112005555522 - 113005555521

输入 - 111555512440
输出 - 数字属于范围 - 5

我已经为数值范围和输入使用了 "long long" 数据类型并完成了它。但是由于我还必须保持性能，有人可以给我一个更好的主意，使输入值保持为字符串，并且范围也将保持为字符串吗？

P.S.: 我可以使用 "char" 指针而不是 std::string.

Answer 1

不要使用字符串，除非在转换任何输入数据时。这将比使用整数类型慢几个数量级。相反，将范围帖子保持在 std::vector<std::uint64_t>.

中

请注意您的矢量将被排序，使用 std::lower_bound 或 std::upper_bound 获取可以找到给定数字的范围。这些函数的运行时间复杂度为 O(log N)，因此速度很快。请仔细阅读这些功能之间的细微差别。

（注意 std::uint64_t 总是 64 位无符号整数，因此适合 12 位数字，但请注意 C++ 编译器 not 一定要支持它；虽然我已经很久没有遇到不支持的了。）

Answer 2

实现此目的的一种方法是创建一个 for 循环并从左侧开始遍历字符串，并在途中消除选项。在您的示例中，前两位数字不消除任何内容，然后下一位数字消除范围 10，因为输入大于范围的下限，然后下一位数字将范围降低到 4 或 5，并且下一位确定范围为 5。您通常不必遍历整个字符串，如果您多次这样做，这对性能有好处。将单个数字转换为整数时，atoi() 函数会派上用场。

示例：假设您将范围存储在数组 number_ranges[10] 中，其中 number_ranges[0] 是第一个范围的下限，number_ranges[1] 是第二个范围的下限（低于它的任何东西仍然在第一个范围内），等等。我们还有一个布尔数组，possible_ranges[10]，其中 true 表示范围仍然可能，而 false 表示不可能。因为我们在开始之前没有消除任何东西，所以一切都应该设置为真。现在，我们需要遍历每个字符串，并适当地消除范围。

for (int i = 0; i < (length of input); i++) {
    for (int j = 0; j < (number of ranges, which is ten); i++ {
        if (input[i] is less than number_ranges[j][i], then there is no way we're in that range, so make that range false)
        if (input[i] is greater or equal to number_ranges[j][i], then there is no way we're in the range below it, so make that false)
        if (everything is false but one, you have your answer, so return it)
    }
}

c ++将大数字字符串映射到数字字符串范围

c++ map large numeric string to numeric string ranges

c++

string

optimization

numeric

range