快速计算数组中 smaller/equal/larger 个元素的方法
Fast way to count smaller/equal/larger elements in array
我需要优化我的算法来计算数组（未排序）中的 larger/smaller/equal 个数字，而不是给定的数字。
我必须多次这样做，给定的数组也可以有数千个元素。
数组不变，数字在变
示例：
数组：1,2,3,4,5
n = 3
- < 的数量：2
- > 的数量：2
- 数量==:1
第一想法：
遍历数组并检查元素是否大于 n 或 < 或 ==。
O(n*k)
可能的优化：
O((n+k) * logn)
首先对数组进行排序（我使用c qsort），然后使用二进制搜索找到相等的数字，然后以某种方式计算较小和较大的值。但是要怎么做呢？
If elements exists (bsearch returns pointer to the element) 我还需要检查数组是否包含这个元素的可能重复项（所以我需要检查这个元素之前和之后，当它们等于 found元素），然后使用一些指针操作来计算更大和更小的值。
如何获取具有指向相等元素的指针的值 larger/smaller 的数量？
但是如果找不到值怎么办 (bsearch returns null)?
如果数组未排序，并且其中的数字没有其他有用的属性，则没有办法击败一次 O(n) 遍历数组并对三个桶中的项目进行计数的方法。
假设您使用时间线性的排序算法（例如基数排序），对数组进行排序后进行二分查找不会比 O(n) 更好。对于基于比较的排序，例如快速排序，时间会增加到 O(n*log2n).
另一方面，如果您需要 运行 对同一组数字进行多次查询，则排序会有所帮助。针对 n 个数字的 k 个查询的时间将从 O(n*k) 的 k 个线性搜索变为 O(n+k*log2n)假设线性时间排序，或 O((n+k)*log2n) 与基于比较的排序。如果 k 足够大，平均查询时间会下降。
因为数组（显然？）没有改变，所以预排序。这允许二进制搜索 (Log(n))
a.) 实现你自己的 bsearch 版本（反正代码会少）
- 您可以使用索引与指针进行内联
- 您不需要指向专门函数的函数指针
b.) 因为你说你想计算匹配的数量，你暗示数组可以包含多个具有相同值的条目（否则你会使用布尔值 has_n）。
- 这意味着您需要对 "n" 数组的开头和结尾进行线性搜索。
- 从中可以计算出小于n和大于n的数。
- 看起来你有一些不成文的算法来选择这些（对于 n=3 你寻找大于和小于 2 和等于 1 的值的计数，所以没有办法给出具体的代码）
c.) 为了进一步优化（以内存为代价），您可以将数据排序到结构的二叉搜索树中，该树不仅包含值，还包含每个值前后的计数和值的数量价值。如果你有很多重复值，它可能根本不会使用更多内存，但如果没有数据集就很难判断。
如果没有描述您的隐藏算法和数据的代码或至少是足够的描述（除了推荐一门或多门数据结构和算法课程之外），这就是我所能提供的帮助。
我需要优化我的算法来计算数组（未排序）中的 larger/smaller/equal 个数字，而不是给定的数字。
我必须多次这样做，给定的数组也可以有数千个元素。
数组不变，数字在变
示例：
数组：1,2,3,4,5
n = 3
- < 的数量：2
- > 的数量：2
- 数量==:1
第一想法：
遍历数组并检查元素是否大于 n 或 < 或 ==。 O(n*k)
可能的优化：
O((n+k) * logn)
首先对数组进行排序（我使用c qsort），然后使用二进制搜索找到相等的数字，然后以某种方式计算较小和较大的值。但是要怎么做呢？
If elements exists (bsearch returns pointer to the element) 我还需要检查数组是否包含这个元素的可能重复项（所以我需要检查这个元素之前和之后，当它们等于 found元素），然后使用一些指针操作来计算更大和更小的值。 如何获取具有指向相等元素的指针的值 larger/smaller 的数量？ 但是如果找不到值怎么办 (bsearch returns null)?
如果数组未排序，并且其中的数字没有其他有用的属性，则没有办法击败一次 O(n) 遍历数组并对三个桶中的项目进行计数的方法。
假设您使用时间线性的排序算法（例如基数排序），对数组进行排序后进行二分查找不会比 O(n) 更好。对于基于比较的排序，例如快速排序，时间会增加到 O(n*log2n).
另一方面，如果您需要 运行 对同一组数字进行多次查询，则排序会有所帮助。针对 n 个数字的 k 个查询的时间将从 O(n*k) 的 k 个线性搜索变为 O(n+k*log2n)假设线性时间排序，或 O((n+k)*log2n) 与基于比较的排序。如果 k 足够大，平均查询时间会下降。
因为数组（显然？）没有改变，所以预排序。这允许二进制搜索 (Log(n))
a.) 实现你自己的 bsearch 版本（反正代码会少）
- 您可以使用索引与指针进行内联
- 您不需要指向专门函数的函数指针
b.) 因为你说你想计算匹配的数量，你暗示数组可以包含多个具有相同值的条目（否则你会使用布尔值 has_n）。
- 这意味着您需要对 "n" 数组的开头和结尾进行线性搜索。
- 从中可以计算出小于n和大于n的数。
- 看起来你有一些不成文的算法来选择这些（对于 n=3 你寻找大于和小于 2 和等于 1 的值的计数，所以没有办法给出具体的代码）
c.) 为了进一步优化（以内存为代价），您可以将数据排序到结构的二叉搜索树中，该树不仅包含值，还包含每个值前后的计数和值的数量价值。如果你有很多重复值，它可能根本不会使用更多内存，但如果没有数据集就很难判断。
如果没有描述您的隐藏算法和数据的代码或至少是足够的描述（除了推荐一门或多门数据结构和算法课程之外），这就是我所能提供的帮助。