arrays - 跨越整个数组长度的最小子序列的长度?
问题描述
我得到一个长度为 N 的整数数组,其中的元素表示它可以覆盖的跨度从 0 到 N-1。因此对于元素 a[i],该元素的范围从 max(ia[i],0) 到 min(i+a[i],N-1)。
如何找到跨越整个空间的最小子序列的长度,即从 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);
解决方案
似乎这个问题可以用简单的贪心算法来解决。
对于每个数组条目,使用start
和finish
字段创建区间 ( a[i].start = i-arr[i] etc
)
按开始字段对间隔进行排序。
finish
在覆盖 0的区间中找到最右边的区间,使maxx=a[i].finish
.
范围内的扫描间隔start
,0..maxx
选择最右边的一个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
推荐阅读
- google-chrome-extension - 我是否必须在 Chrome 扩展程序的 manifest.json 中包含“update_url”:“https://clients2.google.com/service/update2/crx”?
- javascript - 从角度数组顺时针和逆时针获取最接近的角度
- python - 网页抓取雅虎财务统计数据 - 空字段上的代码错误
- javascript - Angular 9 报告打印
- swift - 如何在 SwiftUI 的所有选项卡中使用相同的数据?(可观察对象或环境对象)
- javascript - 如何使用不和谐机器人制作 madlib?(不和谐 JS v12)
- ios - 在 SceneDelegate 中分配的 Observable 属性变为 nil
- python - 如何使用python根据另一列中的条件选择一列中的值?
- outlook - 如何在消息表面中显示 Office 插件任务窗格图标默认值?
- prometheus - 忽略 PromQL 中非重要标签的影响