给定一个数组A1，A2...AN和K，计算有多少子阵列反转计数大于或等于K
Q） 给定阵列A1、A2…an和K计数，有多少子阵列的反转计数大于或等于K.N
所以，我在一次面试中碰到的这个问题。我想出了一个简单的解决方案，用两个for循环(O(n^2)形成所有子数组，并使用O(nlogn)的改进merge sort对数组中的逆序进行计数。这导致了O(n^3logn的复杂性)，我想这是可以改善的。有什么我可以改进的方法吗？谢谢！
共有1个答案
如果我没有错，你可以用O（nlogn）来解决它，使用两个移动指针。
从第一个元素中的左指针开始并移动右指针，直到您有一个子数组
当你到达你已经拥有的那个点
然后将左指针向右移动一个位置并减去它的倒数（同样，在树中查找小于它的元素）。现在，您可以再次执行与以前相同的操作。
摊销分析很容易表明这是O（nlogn），因为两个指针只遍历一次数组，树中的每个操作都是O（logn）。
-
我知道一个O（n2）soln，它能以更好的方式实现吗，因为数组中元素的数量限制非常大
-
我有一个大小为的整数值数组和一个给定的。 我想找到子序列的总数，使得每个子序列的元素总和小于。例如：设 ，，数组的元素为 ，则其总子序列为 作为- 但是，所需的子序列是: 也就是说，不被取，因为它的元素和是，这大于，即
-
当我在一次编码竞赛中解决一个问题时，我发现我需要这样做：给定表示子数组索引的对对于每个元素，计算包含它的子数组的数量。例如： 我们有一个数组＜code＞[7，-2，-7，0，6]，对是＜code＜（0，2）、（1，4）、（2，3）、（0，3）＜/code>，那么结果数组将是＜code>[2，3，4，3，1]，因为第一个元素在子数组＜code>（0，2），＜/code＞（0，3）中，第二个元素在＜c
-
本文向大家介绍计算在C ++中除数等于K的 我们给了两个数字N和K。目标是找到1到N之间具有等于[[，N]]中的K除数的除数。 我们将首先计算范围[1，N]中的K的除数，然后将其存储在变量count中。 现在我们将从i = 1到i = N开始。现在，对于每个数字num = i（使得i！= K），将num的除数计数在范围[1，N]中。并将它们的出现存储在变量除数中。 如果除数=计数，则num在[1，
-
使用百分比表示给定数组中有多少个数字小于或等于给定值。 使用 Array.reduce() 来计算有多少个数字小于等于该值，并用百分比表示。 const percentile = (arr, val) => 100 * arr.reduce((acc, v) => acc + (v < val ? 1 : 0) + (v === val ? 0.5 : 0), 0) / arr.length;
-
给定一个（未排序的）数组S和一些整数k，找到对的数量i， j使得S的范围[i... j] 我在一次采访中收到了这个问题，经过排序后只能得出一个O（nlogn）解。但是，有人告诉我有一个O（n）解。有什么想法吗？