LintCode領扣 題解丨位元組跳動面試題：第k大的子數組

給定一個長度為n的數組a，它有n(n+1)/2​​個子數組。請計算這些子數組的和，然後按照升序排列，并傳回排序後第k個數。

1≤n≤10​^5

1≤a​i≤10^​9

1≤k≤​n(n+1)/2

線上評測位址：

https://www.lintcode.com/problem/the-kth-subarray/?utm_source=sc-tc-sz0810)

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;
}           

}

更多題解參見：[九章算法官網]

https://www.jiuzhang.com/solution/the-kth-subarray/?utm_source=sc-tc-sz0810

​