算法设计与分析（十三）

Count of Range Sum更多技术博客 http://vilins.top/题目Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.Note:A naive algorithm of O(n2) is trivial. You MUST do better than that.Example:Input: nums [-2,5,-1], lower -2, upper 2,Output: 3Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.分析题目的意思是给出一个数组和一个上界和下界要求在连续的区间范围求和使得和在给出的下界和上界的范围内要求给出满足条件的区间的个数。首先分析这个问题这里涉及到区间求和对于这类题目一般的套路是算一个O(n)复杂度的连续求和自然题目也说到通过一般的方法可以在O(n*n)的复杂度求出来但这样显然会超时。这里我们采用分治算法来算首先我们理解以下基本事实对于两个有序的数组我们假设其为n1和n2那么对于n1的一个数如果我们在n2找到最后下标i1使得n2[i1]n1[i]并且有最后下标i2使得n2[i2]n1[i]那么在n2中比n1[i]大的个数为i2-i1。这里我们采用分治算法用到上述思想我们不断将整个数组划分成小的问题在最后一个只有两个元素时开始返回计算对左边数组的每一个元素我们利用上述的思想每处理完一个子问题的时候对其进行归并排序的合并使得问题的左右两边总是有序的这样一来不断往上返回最后得到结果。注意一个问题就是左右两边总是有序的并且我们注意到左边数组的下标总是小于右边数组的下标那么得到的范围也必定是从小下标到大的下标。源码class Solution { public: void mergeSort(vectorlong sum, int b, int m, int e) { int n1 m - b ; int n2 e - m ; vectorlong left(n1, 0); vectorlong right(n2, 0); for(int i 0; i n1; i) { left[i] sum[b i]; } for(int i 0; i n2; i) { right[i] sum[m i]; } int i 0, j 0; for(int k b; k e; k) { if((left[i] right[j])) { sum[k] right[j]; j; if(j n2) { for(int q i; q n1; q) { sum[k1q-i] left[q]; } break; } } else { //cout k k endl; sum[k] left[i]; i; if(i n1) { for(int q j; q n2; q) { sum[k1q-j] right[q]; } break; } } } } int merge(vectorlong sum, int lower, int upper, int low_index, int high_index) { if(high_index - low_index 1) { return 0; } int mid (low_index high_index)/2; int m mid, n mid, count 0; count merge(sum, lower, upper, low_index, mid) merge(sum, lower, upper, mid, high_index); for(int i low_index; i mid; i) { while((sum[m] - sum[i] lower)m high_index) { m; } while((sum[n] - sum[i] upper)n high_index) { n; } count (n - m); } mergeSort(sum, low_index, mid, high_index); //inplace_merge(sum.begin()low_index, sum.begin()mid, sum.begin()high_index); return count; } int countRangeSum(vectorint nums, int lower, int upper) { vectorlong sum(nums.size()1, 0); for(int i 0; i nums.size(); i) { sum[i1] sum[i] nums[i]; } return merge(sum, lower, upper, 0, nums.size()1); } };复杂度分析算法复杂度分析我们这里是基于递归实现的排序的时间复杂度为O(n)在求解的时候递归求解复杂度为logn加上排序的开销总的复杂度应该就是O(nlogn)而空间复杂度是用在对数组进行依次求和的存储复杂度为O(n)。在对左右两个数组合并我用自己实现的函数时效果会差一些而用c标准库的函数的时候也就是用inplace_merge这个函数计算起来会快一点点可能是某些细节的优化问题。更多技术博客 http://vilins.top/