跨越整个数组长度的最小子序列的长度？

Question

我得到了一个长度为 N 的整数数组，其中的元素表示它可以覆盖从 0 到 N-1 的跨度。所以对于元素 a[i] 元素跨越从 max(i-a[i],0) 到 min(i+a[i],N-1).

的范围

如何找到跨越整个 space 即从 0 到 N-1 的最小子序列的 长度；

示例：对于此数组 [1,1,1,3,2,1,1,4]，答案应为 2

这就是我目前所知道的，它并不适用于所有情况

int arr[] = {2,2,1,3,2,1,1,4,1,1,1,1,1,1,1,1,1,1}; // Fails for this case int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; int[] sortedIndices = IntStream.range(0, arr.length) .boxed().sorted((i, j) -> span(arr[j],j,arr.length) - span(arr[i],i,arr.length)) .mapToInt(ele -> ele).toArray(); int i=0; int ans = 0; while (min>0 || max<arr.length-1) { int ind = sortedIndices[i++]; int val = arr[ind]; int tmin = Math.max(0,ind-val); int tmax = Math.min(arr.length - 1, ind+val); if(tmin < min || tmax > max) ans++; min = Math.min(min, tmin); max = Math.max(max, tmax); } System.out.println(ans);

Answer 1

看来这个问题可以用简单的贪心算法解决。

为每个数组条目创建包含 start 和 finish 字段的间隔 (a[i].start = i-arr[i] etc)

按开始字段对间隔进行排序。

在覆盖0的区间中找出最右边finish的区间，使maxx=a[i].finish.

在0..maxx范围内扫描start的区间，选择最右边的finish。

继续。

快速 Python 实施（可能需要更多检查）

ar = [2,2,1,3,2,1,4,4]
n = len(ar)
a = [(max(0, i-ar[i]), min(i+ar[i], n-1)) for i in range(n)]
print(ar)
a.sort()
print(a)
cnt = 0
maxx = -1
left = 0
i = 0
while i < n and maxx < n - 1:
    while i < n and a[i][0] <= left and maxx < n - 1:
        maxx = max(a[i][1], maxx)
        i+=1
    print("maxx ", maxx)
    left = maxx
    cnt += 1

print("cover ", cnt)

[2, 2, 1, 3, 2, 1, 4, 4]
[(0, 2), (0, 3), (0, 6), (1, 3), (2, 6), (2, 7), (3, 7), (4, 6)]
maxx  6
maxx  7
cover  2

跨越整个数组长度的最小子序列的长度？

Length of minimum subsequence that spans entire length of array?

arrays

algorithm

range

sub-array