n****r
发帖数: 120 | |
p*****2
发帖数: 21240 | |
Y**Y
发帖数: 66 | 3 子数组要求连续吧？
两个pointer (i, j),从左到右， sum = A[i] + ... A[j];
i=j = 0;
LOOP:
sum += A[j];
if (sum <= 0) {sum = 0; i=j=j+1;}
else if (sum >= target){
while (sum - A[i] >= target) {
sum -= A[i];
i++;
}
min_subarray = min(min_subarray, j-i+1);
}
j++
【在 n****r 的大作中提到】
: 如题！
|
c****m
发帖数: 179 | 4 楼上的没考虑key为负数的情况吧。应该判断sum是否比min(0, KEY)小？ |
x*********w
发帖数: 533 | 5
快排的partition
【在 n****r 的大作中提到】
: 如题！
|
p*****2
发帖数: 21240 | |
n****r
发帖数: 120 | 7
搬板凳仔细听听，快排partition是啥套路？请详解！
【在 x*********w 的大作中提到】
:
: 快排的partition
|
x*********w
发帖数: 533 | |
n****r
发帖数: 120 | 9 这道题是偶考古出来的F家面试题，没有原题，懊恼。
http://www.mitbbs.com/article_t0/JobHunting/32165741.html
题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
partition。
如果要求子数组连续的话YooY的two pointers思路应该可以，程序正确性我要再看看，
有负数的case处理应该是不行的。
等 xiaoxiaowww (笑笑)的解法！ |
x*********w
发帖数: 533 | 10 假设都是正数：
int GetMinSet(int a[], int n, int k)
{
if (k < 0)
{
int nMax = a[0];
for (int i = 1; i < n; i++)
nMax = max(a[i], nMax);
return nMax >= k ? 1 : 0;
}
//Get the positive part
int i = 0;
int j = n-1;
int nSumPos = 0;
while (i <= j)
{
if (a[i] < 0)
i++;
else if (a[j] >= 0)
{
nSumPos += a[j];
j--;
}
else swap(a[i], a[j]);
}
if (i >= n || nSumPos < k) return 0;
return _inner_min_set(a+i, n-i, k);
} |
|
|
p*****2
发帖数: 21240 | |
n****r
发帖数: 120 | 12 大侠们恕我愚钝，partition完了呢？剩下如何处理正整数部分呢？也就是_inner_min_
set(a+i, n-i, k)如何实现？
比如{5, 1, 4}, target = 8, 因为partition的话就是不要求子数组连续，这时候要排
序吗？ |
r**h
发帖数: 1288 | 13 搭车同问不sort的话有没有更好的方法
min_
【在 n****r 的大作中提到】
: 大侠们恕我愚钝，partition完了呢？剩下如何处理正整数部分呢？也就是_inner_min_
: set(a+i, n-i, k)如何实现？
: 比如{5, 1, 4}, target = 8, 因为partition的话就是不要求子数组连续，这时候要排
: 序吗？
|
h***i
发帖数: 1970 | 14 partition的时候可以顺便把两部分的sum算出来，如果后面的小于key，需要在前面再
找，否则就在后面找。
【在 r**h 的大作中提到】
: 搭车同问不sort的话有没有更好的方法
:
: min_
|
r**h
发帖数: 1288 | 15 对哦，这样就行了
谢谢啦
【在 h***i 的大作中提到】
: partition的时候可以顺便把两部分的sum算出来，如果后面的小于key，需要在前面再
: 找，否则就在后面找。
|
b*****u
发帖数: 648 | |
x*********w
发帖数: 533 | 17
这个不是重点吧
【在 b*****u 的大作中提到】
: 快排的pivot怎么选？
|
b*****u
发帖数: 648 | 18 我在想怎么确保每次范围都会缩小，如果恰巧选了个极值所有数都落在一侧了呢？
【在 x*********w 的大作中提到】
:
: 这个不是重点吧
|
p*****2
发帖数: 21240 | 19
worst case N^2
【在 b*****u 的大作中提到】
: 我在想怎么确保每次范围都会缩小，如果恰巧选了个极值所有数都落在一侧了呢？
|
r**h
发帖数: 1288 | 20 范围内随机取一个数
见CLRS
【在 b*****u 的大作中提到】
: 我在想怎么确保每次范围都会缩小，如果恰巧选了个极值所有数都落在一侧了呢？
|
b*****u
发帖数: 648 | 21 对啊，所以并不一定比用heap的nlogn好
【在 p*****2 的大作中提到】
:
: worst case N^2
|
p*****2
发帖数: 21240 | 22
按照CC150的说法可以做到linear。但是算法会很复杂。让参见CLRS
【在 b*****u 的大作中提到】
: 对啊，所以并不一定比用heap的nlogn好
|
