s****e
发帖数: 638 | 1 输入是一个数列长度N，和一个数L。 求一个cover最多的数字，并且长度为L的 interval。
看着是道简单题，先排序，然后两重循环，找出cover数字最多的interval. 这个题有
陷阱没有？ | w****o
发帖数: 2260 | 2 能否给个例子？
这里interval指的是什么？什么是"cover最多的数字"?
还有interval [5 6]的长度是1 还是2? interval [5 5]的长度是0 还是1?
xiexie!
interval。
【在 s****e 的大作中提到】
: 输入是一个数列长度N，和一个数L。 求一个cover最多的数字，并且长度为L的 interval。
: 看着是道简单题，先排序，然后两重循环，找出cover数字最多的interval. 这个题有
: 陷阱没有？
| s****e
发帖数: 638 | 3 输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
是0吧。
【在 w****o 的大作中提到】
: 能否给个例子？
: 这里interval指的是什么？什么是"cover最多的数字"?
: 还有interval [5 6]的长度是1 还是2? interval [5 5]的长度是0 还是1?
: xiexie!
:
: interval。
| w****o
发帖数: 2260 | 4 谢谢，这个好像不是唯一解。以你的例子来说，返回[5, 9]也是一样的。对吧？
【在 s****e 的大作中提到】
: 输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
: L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
: 是0吧。
| w****o
发帖数: 2260 | 5 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
我觉得排除排序后,可以做到O(nlgn).
大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
_bound，
这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
【在 s****e 的大作中提到】
: 输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
: L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
: 是0吧。
| l*********8
发帖数: 4642 | 6 if the array is already sorted, O(n) algorithm can find the max coverage
interval. Just replace your binary search to sequential search.
upper
【在 w****o 的大作中提到】
: 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
: 我觉得排除排序后,可以做到O(nlgn).
: 大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
: _bound，
: 这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
| s****e
发帖数: 638 | 7 觉的你说的是对的。
upper
【在 w****o 的大作中提到】
: 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
: 我觉得排除排序后,可以做到O(nlgn).
: 大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
: _bound，
: 这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
| w****o
发帖数: 2260 | 8 对，排序后，就是O(n)了。我自己写了一个，应该是对的。不过有点儿ugly.
typedef struct {
int start;
int end;
} Interval;
int intcomp (const void * p1, const void * p2)
{
return *(int *)p1 - *(int *)p2;
}
Interval find_interval_cover(int a[], int N, int L)
{
Interval result;
int i, j;
int count = 0;
qsort(a, N, sizeof(int), intcomp);
print_arr(a, N);
for (i = 0, j = 0; j < N; ) {
if (a[j] <= a[i] + L) {
j++;
} else {
if (j- i > count) {
count = j - i;
result.start = a[i];
result.end = a[i] + L;
}
i++;
}
}
if (j- i > count) {
count = j - i;
result.start = a[i];
result.end = a[i] + L;
}
printf("count = %d\n", count);
return result;
}
【在 l*********8 的大作中提到】
: if the array is already sorted, O(n) algorithm can find the max coverage
: interval. Just replace your binary search to sequential search.
:
: upper
| l*****a
发帖数: 14598 | 9 这个题显然跟有没有序没有任何关系
为什么要排序处理呢？排序之后显然破坏了原来数组啊
结果怎能正确？ | l*********8
发帖数: 4642 | 10 没有说不能改变原来数组吧
【在 l*****a 的大作中提到】
: 这个题显然跟有没有序没有任何关系
: 为什么要排序处理呢？排序之后显然破坏了原来数组啊
: 结果怎能正确？
| | | l*****a
发帖数: 14598 | 11 人家要得结果是依赖于输入顺序的
你给改了算咋回事？
【在 l*********8 的大作中提到】
: 没有说不能改变原来数组吧
| l*********8
发帖数: 4642 | 12 结果跟输入顺序没有关系吧。 不然interval是怎么cover数字的？
【在 l*****a 的大作中提到】
: 人家要得结果是依赖于输入顺序的
: 你给改了算咋回事？
| l*****a
发帖数: 14598 | 13 1,2,3,4,5,3,4,5,6,2,1,7,5,3,4
假定找长为４的interval,有如下这些。。
你就想办法算出相应数字出现数目好了
1,2,3,4
2,3,4,5
3,4,5,3
4,5,3,4
.....
【在 l*********8 的大作中提到】
: 结果跟输入顺序没有关系吧。 不然interval是怎么cover数字的？
| l***i
发帖数: 1309 | 14 maintain a BST with elements in current size L window, when you slide window
from left to right, it amounts to one insertion and one deletion. So a
balanced binary tree with extra count of each element will do it in O(logn)
per move, and a total of O(nlogn) | l*********8
发帖数: 4642 | 15 假如输入是 1,1,2,2,3,3,4,4,4,5,5,5,6,7
输出结果有不同吗？
【在 l*****a 的大作中提到】
: 1,2,3,4,5,3,4,5,6,2,1,7,5,3,4
: 假定找长为４的interval,有如下这些。。
: 你就想办法算出相应数字出现数目好了
: 1,2,3,4
: 2,3,4,5
: 3,4,5,3
: 4,5,3,4
: .....
| p*****2
发帖数: 21240 | | l*********8
发帖数: 4642 | 17 呵呵，我现在明白，你意思是，求哪个sub-array里面的unique numbers多？
【在 l*********8 的大作中提到】
: 假如输入是 1,1,2,2,3,3,4,4,4,5,5,5,6,7
: 输出结果有不同吗？
| l*****a
发帖数: 14598 | 18 yes,I think that is what they want
just like the famous issue
"find the minimum slide windows contains all the given words"
【在 l*********8 的大作中提到】
: 呵呵，我现在明白，你意思是，求哪个sub-array里面的unique numbers多？
| l*********8
发帖数: 4642 | 19 Thanks.
"find the minimum slide windows contains all the given words" 这个问题比楼
主贴的要难，因为window size是不定的。
【在 l*****a 的大作中提到】
: yes,I think that is what they want
: just like the famous issue
: "find the minimum slide windows contains all the given words"
| w****o
发帖数: 2260 | 20 lolhaha, longway2008,
根据你们的理解，这道题是不是找长度为 L 的subarray中含有最多的不同数字的那个
subarray?
xiexie!
【在 l*****a 的大作中提到】
: yes,I think that is what they want
: just like the famous issue
: "find the minimum slide windows contains all the given words"
|
|
