【LeetCode/LintCode】 題解丨字節跳動試題：第k大的子數組
- 2020 年 8 月 10 日
- 筆記
給定一個長度為n的數組a，它有n(n+1)/2個子數組。請計算這些子數組的和，然後按照升序排列，並返回排序後第k個數。
- 1≤n≤10^5
- 1≤ai≤10^9
- 1≤k≤n(n+1)/2
在線評測地址：點擊此處前往
Example1
Input:
[2,3,1,4]
6
Output:5
Explanation:
我們可以得到所有子數組的和是 [1,2,3,4,4(3 + 1), 5(1 + 4), 5(2 + 3), 6(2 + 3 + 1), 8(3 + 1 + 4), 10(2 + 3 + 1 + 4)]。其中第六個是5。【題解】
演算法
二分+two pointer
演算法分析
我們可以看到，題目需要求和第k
k大的子區間，而我們的區間總個數共有n(n+1)/2個，當n為10^5時這個數高達10^10級別。我們顯然不能暴力的枚舉每一個區間和然後排序。
演算法思路
我們注意到，所有數字的和不超過10^14，這個範圍可以讓我們想到使用二分最終的答案進行求解。
二分要求解的問題是：對於給定的和x，求有多少個區間的和小於x，小於等於x。這需要我們在O(n)的時間複雜度內進行求解。由於數組內所有數都是正數，我們自然的可以想到同向雙指針求解。噹噹前區間的和大於k，就移動左指針，否則移動右指針。
時間複雜度
O(nlog(n))
public class Solution {
/**
* @param a: an array
* @param k: the kth
* @return: return the kth subarray
*/
private int check(long x, int[] a, long k) {
long tmp1 = 0, tmp2 = 0, now = a[0];
int l = -1, r = 0, n = a.length;
long all = (long)n * (n + 1) / 2;
while (l <= r && r < n)
{
if (now >= x) {
if (now == x) {
tmp2++;
} else {
tmp1++;
}
tmp1 += n - r - 1;
l++; now -= a[l];
}
else {r++; if (r < n) now += a[r];}
}
if (all - tmp1 - tmp2 < k && all - tmp1 >= k) return 0;
if (all - tmp1 - tmp2 >= k) return 1;
else return -1;
}
public long thekthSubarray(int[] a, long k) {
// wrrite your code here
int n = a.length;
long sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
long l = 1, r = sum;
while (l <= r) {
long mid = (l + r) / 2;
int flag = check(mid, a, k);
if (flag == 0) {
return mid;
}
if (flag == 1) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
return -1;
}
}更多題解參見：
