1

我需要从整数列表中查找一个整数。我对它们进行排序并使用 lower_bound 来查找给定整数的范围。这需要 O(lgn)。有什么办法比这更好吗？

以下是改进的提示。

  1. 给定列表总是正整数
  2. 列表是固定的。没有插入或删除。

一种方法是创建一个数组并索引到该数组。这可能不节省空间。我可以使用 unordered_map 吗？我应该定义什么哈希函数？

// Sort in reverse order to aid the lookup process
vector<unsigned int> sortedByRange;
//... sortedByRange.push_back(..)
sort(sortedByRange.begin(), sortedByRange.end(), greater);
Range = (sortedByAddress_.begin() - sortedByRange.end();
std::cout<<"Range :"<<Range<<std::endl;    //prints 3330203948

std::pair<unsigned int, unsigned int> lookup(unsigned int addr){
    pair<unsigned int, unsigned int> result;
    vector<unsigned int>::iterator it = lower_bound(sortedByRange.begin(), 
                                           sortedByRange.end(), addr);
    result.first = *it;
    result.second = *(it++);
    return result;
}
4

3 回答 3

1

如果总范围不是很大，您可以构建一个任何方便大小的采样索引数组（您想投入多少 RAM？）

因此，例如，如果数据的总范围是 256M，并且您有一个空闲的兆字节，那么您存储数据范围的每 1K 间隔的位置。然后对于任何给定的数据点，你做一个 O(1) （实际上是 O(2) :) ）探测索引数组以找到该数据点的最低和最高合理范围，然后你可以做最低限度范围。如果您的范围在大小上没有太大变化，那应该会给您平均恒定时间查找。

如果您不想在问题上投入那么多内存，您可以尝试基于平均范围大小和模糊因子的一对线性估计。如果结果不包含特定数据点，则可以回退到完整的二进制搜索；否则，同样，限制范围内的二进制搜索应该是平均线性时间。

这是第一个建议，以防挥手不够清晰。完全未经测试的代码，甚至没有尝试编译它，并且至少可以说整数类型的使用是草率的。如果你使用它，试着让它更漂亮。我也应该（但没有）将索引范围的开始限制为 *begin_; 如果它显着大于 0，则应该修复它。

// The provided range must be sorted, and value_type must be arithmetic.
template<type RandomIterator, unsigned long size>
class IndexedLookup {
 public:
  using value_type = typename RandomIterator::value_type;
  IndexedLookup(RandomIterator begin, RandomIterator end)
    : begin_(begin),
      end_(end),
      delta_(*(end_ - 1) / size) {
    for (unsigned long i = 0; i < size; ++i)
      index_[i] = std::lower_bound(begin_, end_, i * delta_) - begin_;
      // The above expression cannot be out of range
    index_[size] = end_ - begin_;
  }

  RandomIterator lookup(value_type needle) {
    int low = needle / delta_;
    return std::lower_bound(index_[begin_ + low],
                            index_[begin_ + low + 1],
                            needle);
  }

 private:
  RandomIterator begin_, end_;
  value_type delta_;
  std::array<int, size + 1> index_;
}
于 2012-09-26T04:58:07.697 回答
0

方法一：如果只需要知道给定的数字是否在列表中，并且最大值不是太大，可以考虑使用位域。查找将是 O(1) 操作。

方法 2：如果值的范围很大（其中有小整数和大整数），但列表大小不大（例如几千），您可以尝试（以编程方式）制作一个哈希函数

  1. 与列表中的值是一对一的；
  2. 将给出一个 range 0...的值，N + m并且m 足够小；
  3. 计算起来相对便宜。

然后可以将常量列表的值放入由哈希值索引的数组中，以便快速检查给定输入值的包含情况。如果列表中有漏洞（m非零），则应使用特殊值（例如-1）来指示这些漏洞。

包含测试：对于给定的输入 1. 计算哈希值；2.如果哈希值的值超出范围，则输入不在列表中；3. 否则，当且仅当由哈希值索引的生成数组中的值与输入值相同时，输入才属于列表。

如何制作哈希函数在 SO 中值得另一个问题（对于字符串值，存在为此目的生成工具的工具）。:-)

限制：如果列表不是在编译时创建的，而是在程序运行时计算或接收的，则此方法不适用。此外，如果此列表经常更改，则生成散列函数和代码所需的计算时间可能会使此方法不适合。

于 2012-09-26T03:53:06.463 回答
0

Javascript

let searchRangeInterger = function(nums, target) {
  let res = [-1, -1];
  let leftSide = find(nums, target, true);
  let rightSide = find(nums, target, false);
  if (!nums.length) return res;
  if (leftSide > rightSide) return res;
  return [leftSide, rightSide];
};

let find = function (nums, target, findLeft) {
  var left = 0;
  var right = nums.length - 1;
  var mid = 0;

  while (left <= right) {
    mid = Math.floor((left + right) / 2);
    if (nums[mid] > target || (findLeft && nums[mid] === target)) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return findLeft ? left : right;
};
于 2022-02-24T05:55:48.593 回答