y****n
发帖数: 743 | 1 这个算法有如下问题：
1. 某些时候会返回错误结果
比如输入：{ 1, 1, 0 }，结果中0也别认为是missing。
2. 两重循环，算法的复杂度是O(n^2)
3. 执行结束后，原数组的内容（循序）被更改。 |
|
S****h
发帖数: 115 | 2 yishan, 这是用C#写的么？
提点建议：
1.代码会有抛数组越界的情况，test case{ 1, 1};
2.你的代码可以读我觉得真的不强//或者是我没有抓到你的思路，还请加些comments
peking2写dp代码浅显易懂，霸气威武。建议参考 |
|
c****9
发帖数: 164 | 3 大小为K的min heap去扫整个数组，O（MN）*logk，第一时间只有这个想法 |
|
w****x
发帖数: 2483 | 4 有种解法是基于数值的2分, 实现起来也很绕. 原题是给两个排序的数组 A, B. 如果a
->A, b->B, 求第k大的a + b, 可以化成杨氏矩阵求解, 没记错因该是Google的题, 我
见过最难的题之一 |
|
w***y
发帖数: 6251 | 5 我当时想的是， 在heap里面放的node，除了排序用的key, 还存放数组指针 |
|
t**********h
发帖数: 2273 | 6 你的这个题目是150上的原题，O（M+N）可以做。
另外之前版上有讨论一道和这个相似的题，但是matrix本身有一个附加条件，即下一行
的对应的element比这一行的这个element也要大。所以最终就转化为一个一维排好序的
数组了，然后二分O（lgn） |
|
t********e
发帖数: 344 | 7 我觉得明明有solution啊，就用quick sort的思想，大家看看对不对，还是我理解题目
有问题？
先扫一遍数组A[n]，知道有多少负数，假设有m个
把m视为pivot的位置，设两个指针，一个初始指向A[0], 另一个初始指向A[m]:
i=0, j=m
if A[i]>0 and A[j]<0, swap them
if A[i]<0,i++
if A[j]>0,j++
直到i=m-1 或j = n-1
这样就好了是O(n) time, O(1)space
对挖？ |
|
h********g
发帖数: 155 | 8 先考虑如下基本问题：
假定一个数组前N个数是正数，后M个数是负数，如何把M个负数全部移到头部，N个正数
全部移到尾部，同时不改变正数与负数的相对次序？
其实用 N+M 次交换操作就可解决上面问题。因为每次移动一个负数时，你不需要只向
前移一位，而是可以－次移很多位。
比如你有：
３ ２ ５ －１ －２
你可以把２与－１交换，５ 与－２交换得到：
３ －１ －２ ２ ５
再把 ３ 与 －１ 交换
－１ ３ －２ ２ ５
再把 ３ 与 －２ 交换得到
－１ －２ ３ ２ ５
于是移位完成，用了４次交换
于是当 M 能整除 N 时， 用上面的办法其实只交换N次就可以完成了，当M不能整除N时
，你也可以用数学归纳法证明只要M+N次交换就够了。
那么现在你再回过头来看我的算法，就会发现它所需的总操作数最多是：
(l(k-1, k)+1)+(l(k-2,k-1)+2)+(l(k-3, k-2)+3)+...(l(1, 2)+k-1)+(l(0, 1)+k)
其中l(i-1, i)表示第i-1个负数和第i个负数之间所含的正数的个数,
所有的l(i-1, i) 1<=i<=k 的和最多是 N,
所以... 阅读全帖 |
|
h********g
发帖数: 155 | 9 不客气, 你不需要建表去存储负数的位置，只需一个变量，扫一遍数组，找出最后一个
负数的位置，用该变量存储这个位置, 用O（N）时间。
然后从这个位置往后一个一个的查，查到下一个负数就是倒数第二个负数，然后用我提
到的方法把最后一个负数移到到倒数第二个负数紧接下来的位置。然后再从这个位置出
发往后找下一个负数，。。。 然后重复这一过程。
问题的关键是你从最后一个负数的位置开始向后查找，永远不需要再向前移动，而是一
直向后移，碰到下一个负数停一下，等操作完毕后继续向后移寻找下一个负数，所以最
后累计所用的时间也是O（N）。 |
|
S*******e
发帖数: 379 | 10 假设有一个数组：
a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn
要变成
a1 b1 a2 b2 a3 b3 a4 b4 .. an bn
要求in place, 比O(n^2)更好的算法。 |
|
X*K
发帖数: 87 | 11 怎么是想当然呢，你给个in-place O(n)的算法，那么同样那可以用来
把两个排好序的数组in-place归并，那恭喜你，你找到了in-place的
merge sort算法，牛大了。 |
|
l**********g
发帖数: 426 | 12 数组 3, 5,1, 8, 9, 7, 0, 2
找到 3, 1, 0, 2 ----最长序列
要求复杂度好于 O(nlog(n))
有hashmap记录间隔的解法，写起来蛮复杂。
大侠指点。 |
|
s*******f
发帖数: 1114 | 13 jingo 你狠彪悍！！
//码遍本版
//: 数组 3, 5,1, 8, 9, 7, 0, 2
//: 找到 3, 1, 0, 2 ----最长序列
//: 要求复杂度好于 O(nlog(n))
//i use static linked list here
//change map to hash_map, then O(n)
struct NodeInfo{
int data;
int next;
bool has_pre;
NodeInfo(int d):data(d), next(-1), has_pre(false){ }
NodeInfo(){}
};
vector MaxForSeq(int a[], int len){
vector ret;
vector vn(len);
map mp; //data to index in vector vn
for (int i = 0; i < len; ++i){
if (mp.... 阅读全帖 |
|
c*******r
发帖数: 610 | 14 果然是不对的：）
如果数组里有负数，就是错的....（可能还有很多其他情况都不对，没仔细想）
比如：A[] = {5,-1,5,0,10,20,1,15,4,18}， 返回1，应该返回0.
看来O（n）解法没那么简单.... |
|
Z*****Z
发帖数: 723 | 15 Given an array, find the longest subarray which the sum of the subarray less
or equal then the given MaxSum.
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6}
感觉用两个指针一前一后扫一遍数组就行了？求证。。。
出处：
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
2821_2.C0/%C0%B4%B5%C0%C4%D1%D2%BB%B5%E3%B5%C4%CC%E2 |
|
v****c
发帖数: 29 | 16 大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i
2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,-1,10,
-7} |
|
j********e
发帖数: 1192 | 17 首先，partial sum你计算错了，最后一个数是4，不是5.
最好的结果是{-1, 10, -7, 9, -8}.
算法本身好像没有问题。
大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i
2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,... 阅读全帖 |
|
v****c
发帖数: 29 | 18 整个数组都是啊
一开始q指向最后一个，然后就不动了，p一直走到第一个 |
|
s*******y
发帖数: 44 | 19 这个最长的序列不是{-1,10,-7,9,-8}吗？为什么是{1,-1,10,-7}？
另外为什么partial sum从第一个数开始找递增序列？S中可能有负数的，极端一点，A
全是负数，要求和小于一个负数，这个递增序列就找不到了。
大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i
2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
... 阅读全帖 |
|
n****r
发帖数: 120 | 20 我目前的做法是去A，B数组的中位数进行比较，然后根据最大的中位数左边的元素个数
和k进行比较来丢弃A或B的一端数据，递归的缩小范围。
还有其他更好的更简洁的解法没有？ |
|
c********t
发帖数: 5706 | 21 俺证实了你的想法可行，而且直观，其实用二维数组即可，不用list.
wiki上的我怎么也实现不了 |
|
c********t
发帖数: 5706 | 22 俺证实了你的想法可行，而且直观，其实用二维数组即可，不用list.
wiki上的我怎么也实现不了 |
|
|
|
D**f
发帖数: 439 | 25 假想在数组结尾append一个0，作为pivot，然后以此作quick sort 的partition步骤。
其实append那步可以省略。 |
|
b*****u
发帖数: 648 | 26
所谓不稳定是说相等的数字一个被选中pivot后相对于其他几个的位置不定吧
如果数组里没有0，那么添个0进去作pivot 快排一轮还是不稳定的吗？ |
|
j******2
发帖数: 362 | 27 可是如果需要设的不是default值呢？比如我想要个数组，100个test，都是t=5的，能
一行定义出来吗？ |
|
d**********1
发帖数: 37 | 28 我知道动态alloc没有这样的问题，因为可以check分配成功与否
我遇到一个bug，内存中的连续15个bytes corrupted了，怀疑是这个静态申请的数组侵
犯了别人的内存。
这种overflow按照道理说在运行时应该报错，但是会不会不报错，而用了别人的地址呢 |
|
O******i
发帖数: 269 | 29 你这个数组是函数外定义的全局变量？量还是函数里定义的局部变量？或者是静态变量？
MAXPATHLEN多大？如果比较小，应该是没有问题的。
你可以改为动态分配，看看这个bug还有没有
如果是局部变量，改为全局变量或者静态变量，看看结果如何 |
|
d****r
发帖数: 80 | 30 一道面试题：
给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
不能分的时候返回空值。能分的时候给出一个解就行。
我只能想到三进制，有没有更优化的方法？ |
|
j*****y
发帖数: 1071 | 31 二等分数组是可以用 dp的，
三等分的话，可不可以证明：
如果可以三等分的话，如果拿出一个子集的和是 1/3的和，那么剩下的一定可以二等分？
这个可以证明是正确的话，那么就是两次 dp 了 |
|
z*******8
发帖数: 30 | 32 我觉得这个思路挺好，有点递归的意思，不过条件有点强吧。
比如
1,2,3,
0,0,5,
0,0,7
这个数组就是不能三分的。
分？ |
|
d**********n
发帖数: 132 | 33 请大牛明示，这道题的dp是找一个解吧？用一个二维数组来储存当前element可能生成
的和 |
|
c********t
发帖数: 5706 | 34 根据数组左右jump，最后判断能不能到0点
求原题！
记得二爷好像在哪里总结过。 |
|
x******a
发帖数: 6336 | 35 你可以先扫一遍。。
你也可以考虑用6.
找出一个和是sum／2的数组 |
|
c********l
发帖数: 8138 | 36 数组shuffle，经典的Fisher and Yates的算法是
public static void shuffle(List list, Random rnd) {
int size = list.size();
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
}
}
如果将
swap(list, i-1, rnd.nextInt(i));
改成
swap(list, i-1, rnd.nextInt(N));
会出错。
具体出错的原因是什么？怎么描述这种现象？ |
|
s**x
发帖数: 7506 | 37 第一个是java 的吧？c 里面世纪上没有数组参数这个概念，就是一指针.
Void f(int *a)
Void f(int a[]) 应该是等价的。
★ 发自iPhone App: ChineseWeb 7.8 |
|
j******2
发帖数: 362 | 38 巨大的数组，不能放进内存的，怎么shuffle？ |
|
b******7
发帖数: 92 | 39 不能先分段shuffle，再shuffle段id，这样不均匀。比如考虑数组为aaaaabcdef，若按
照这个思路，则无论怎么shuffle，这5个a都会在一起。
我的考虑和racolas一样，先将N个元素shuffle到M个文件中，再在M个文件内shuffle，
最后合并。
定义每个文件当前可容纳元素个数r[i],i=0...M-1,初始时所有r[i]都为N/M
从磁盘上读取N个元素，设当前为第k个元素，则根据rand[1,N-k]落入{r[0],r[0]+r[1]
,r[0]+r[1]+r[2],...}中的哪一个决定第k个元素写入哪个文件，并且相应的文件可容
纳个数减1。 |
|
s**********r
发帖数: 8153 | 40 怎么做阿？我只会用2－d array做，忽然看见人家1-d的做的非常好。
可是没看懂阿，怎么用滚动数组阿？ |
|
s*****n
发帖数: 994 | 41 不要用bool数组，用int set来存unvisted |
|
l*n
发帖数: 529 | 42 这已经是最好的解法了啊，有一点他说错了，这个不是O(n^2)，已经是O(n)了，因为环
内visit一次，环外循环的时候判断visited一次，就是O(2n)。空间方面可以是O(n)，
也可以是借助原数组达到O(1)。 |
|
s*****n
发帖数: 994 | 43 不要用bool数组，用int set来存unvisted |
|
l*n
发帖数: 529 | 44 这已经是最好的解法了啊，有一点他说错了，这个不是O(n^2)，已经是O(n)了，因为环
内visit一次，环外循环的时候判断visited一次，就是O(2n)。空间方面可以是O(n)，
也可以是借助原数组达到O(1)。 |
|
s*****4
发帖数: 25 | 45 是啊 如果没有"每个数组元素的值都不同"这个条件 应该就要做n次dfs 而且每次都
reset visited array?
这样的话 复杂度就是O(n^2) |
|
c*****e
发帖数: 67 | 46 给定两个排序数组A和B，找到A与B中元素最小差值。
如A={0,3}, B={2,7,9}, 结果是1（A中的3和B中的2的差值）
想到一个O(nlogn)的解法：取A中的每一个值，在B中进行binary search。贴个Java代
码如下。不知道有没有更好的解法。
public int minDiff(int[] a, int[] b) {
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
int n = a[i];
int low = 0;
int high = b.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (b[mid] == n)
return 0;
... 阅读全帖 |
|
s********x
发帖数: 914 | 47 这个完全可以进一步优化，每次的low可以设为在B中找的元素.而且A应该选length小的
那个数组。 |
|
|
Q*****a
发帖数: 33 | 49 没想到什么比O(n^2)好的方法，毕竟是partially order, 不是total order
但到不了O(n^2*l), 只是O(n^2 + nl).只需要过一遍string计算sign就可以了，另外将
数组按长度从大到小排列，提前剪枝也可以优化一些，但复杂度还是O(n^2)
const int INT_BITS = sizeof(int) * 8;
const int DATA_LEN = 256/INT_BITS;
class Int256 {
vector data;
public:
Int256(): data(DATA_LEN, 0) {
}
Int256(string s): data(DATA_LEN, 0) {
for (auto c: s) {
Set((unsigned char)c);
}
}
void Set(int l) {
data[l/INT_BITS] |= 1 << (l%INT_BITS);
}
... 阅读全帖 |
|
a*******3
发帖数: 13 | 50 updates A so that if x appears m times in A, it appears exactly min(2,m)
times in A.
这题意思不应该是如果一个数在数组里面正好出现了m次，才把这个数的出现次数调整
为min(2.,m)么？如果这个数出现次数不等于m次不应该全部保留下来么？
还是说我理解有问题。。？ |
|
