data-structures 相关问题

假设给你一个 n 大小的数组 A 和一个整数 k。现在你必须遵循这个函数：长长和(int k) { 长长和 = 0; for(int i=0; i 假设给你一个 n 大小的数组 A 和一个整数 k。现在你必须遵循这个功能： long long sum(int k) { long long sum = 0; for(int i=0; i<n; i++) { sum += min(A[i], k); } return sum; } 求和最有效的方法是什么？如果我得到 m(<=100000) 查询，并且每次都给出不同的 k，它会变得非常耗时。如果查询集随着每个 k 的变化而变化，那么你就不能比 O(n) 做得更好了。优化的唯一选择是使用多个线程（每个线程对数组的某个区域求和）或至少确保编译器正确矢量化您的循环（或使用内在函数手动编写矢量化版本）。但是如果查询集是固定的并且仅改变k，那么您可以通过使用以下优化在 O(log n) 中完成。预处理数组。对于所有k，此操作仅执行一次：对元素进行排序制作另一个相同长度的数组，其中包含部分和例如： inputArray: 5 1 3 8 7 sortedArray: 1 3 5 7 8 partialSums: 1 4 9 16 24 现在，当给出新的k时，您需要执行以下步骤：对 k 中给定的 sortedArray 进行二分查找——返回最大元素 <= k 的索引结果是partialSums[i] + (partialSums.length - i) * k 你可以做得更好如果你可以对数组进行排序A[i]并准备一次辅助数组。想法是：计算有多少项小于k，然后通过公式计算等效总和：count*k 准备一个辅助数组，它将直接给出优于k的项目的总和准备工作第1步：对数组进行排序 std::sort(begin(A), end(A)); 第2步：准备辅助数组 std::vector<long long> p_sums(A.size()); std::partial_sum(rbegin(A), rend(A), begin(p_sums)); 查询 long long query(int k) { // first skip all items whose value is below k strictly auto it = std::lower_bound(begin(A), end(A), k); // compute the distance (number of items skipped) auto index = std::distance(begin(A), it); // do the sum long long result = index*k + p_sums[index]; return result; } 查询的复杂度为：O(log(N))，其中N是数组A的长度。准备工作的复杂程度是：O(N*log(N))。我们可以使用基数排序到 O(N)，但我认为这对你的情况没有用。参考文献 std::sort() std::partial_sum() std::lower_bound() 你所做的看起来绝对没问题。除非这确实是绝对时间关键的（即客户抱怨你的应用程序太慢并且你测量了它，而这个函数就是问题所在，在这种情况下你可以尝试一些不可移植的向量指令，例如）。通常，你可以通过从更高的层次来看待事情来更有效地做事。例如，如果我写 for (n = 0; n < 1000000; ++n) printf ("%lld\n", sum (100)); 那么这将需要很长的时间（五万亿的添加）并且可以更快地完成。如果一次更改数组 A 的一个元素并每次都重新计算总和，则效果相同。假设数组 A 有 x 个不大于 k 的元素，集合 B 包含大于 k 且属于 A 的元素。则函数 sum(k) 的结果等于 k * x + sum_b ，其中 sum_b 是属于 B 的元素之和。可以先对数组A进行排序，然后计算数组pre_A，其中 pre_A[i] = pre_A[i - 1] + A[i] (i > 0), or 0 (i = 0); 然后对于每个查询k，在A上使用二分查找找到不大于k的最大元素u。假设u的索引为index_u，则sum(k)等于 k * index_u + pre_A[n] - pre_A[index_u] 。每个查询的时间复杂度是 log(n)。如果数组A可能会动态变化，可以使用BST来处理。

c++ arrays data-structures

回答 4 投票 0

如何将值列表合并到hashmap中的同一个Key？

如何将值列表合并到HashMap中的同一个键上？如果我使用上述逻辑，我将得到以下结果作为输出： {Adam=[[主题，计算机科学]，[主题，计算机科学]]} 但我...

java arraylist data-structures hashmap

回答 1 投票 0

检查数组中是否有3个数字异或等于0

给定 N 个实数数组 x_1, x_2, ..., x_n，检查是否存在 1 <= i,j,k <= n such that x_i ⊕ x_j ⊕ x_k = 0, where ⊕ is XOR operation. This is college homework and it has to be done...

algorithm data-structures xor trie

回答 1 投票 0

data-structures 相关问题

最新问题