|
j*****u 发帖数: 1133 | 2 没有仔细看wiki,如果要返回数组是需要2个array的
比如这个例子: 5 6 7 1 2
最终M = {3, 4, 2},如果没有P,返回的数组就成了1 2 7而不是5 6 7了。 |
|
x******g 发帖数: 41 | 3 我的理解,
算mid
然后从用mid的值把sum的数组分段得到k_n
如果k_n>k,说明mid小了,在upper right重复搜索
反之在left搜索
比如
2 2 2 2 2 5 5 5 1 1 1 1 1
sum:2 4 6 8 10 15 20 25 26 27 28 29 30
lo = 5, hi = 30
mid = 17
17可以把sum数组分成2段,
2 4 6 8 10 15 20 | 25 26 27 28 29 30
所以17太大了,lo=5,hi=16
mid = 10
正好3段,结束 |
|
g*********s 发帖数: 1782 | 4
算mid
然后从用mid的值把sum的数组分段得到k_n
怎么个分段法?k_n是什么?
如果k_n>k,说明mid小了,在upper right重复搜索
反之在left搜索
比如
2 2 2 2 2 5 5 5 1 1 1 1 1
sum:2 4 6 8 10 15 20 25 26 27 28 29 30
lo = 5, hi = 30
mid = 17
17可以把sum数组分成2段,
2 4 6 8 10 15 20 | 25 26 27 28 29 30
这个分段怎么来的?和17有什么关系?
所以17太大了,lo=5,hi=16
mid = 10
正好3段,结束 |
|
g*********s 发帖数: 1782 | 5 正整数的数组x[1..n],分成k段,找分段法,minimize the maximum sum of any
pieces,
minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
dp:
f(n,k) = min { max { f(i,k-1), sum(x[j]) | i = 1..n, j = i+1..n } }
这个复杂度是O(K*N^2),可以加速到O(K*NlgN)?
如果输入改成非负整数数组呢?
如果改成任意整数呢?
二分法要求必须是正整数吧? |
|
n*******n 发帖数: 3 | 6 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 O(nlogk), n为所有
integer的个数. 证明如下:
一般常识是sort n个integer最快是O(nlogn). 所以把n个integer分成k组,每组分别
sort,再合起来,不可能比O(nlogn)更快。 n = k * m
分别sort k 个 size 为 m的数组共需时间 k * O(mlogm) = O(nlogm). 所以merge k个
数组的时间不可能小于 O(nlogn)- O(nlogm) = O(nlog(n/m)) = O(nlogk) .
楼上各位已经找到最优解了。 |
|
n**z 发帖数: 155 | 7 如果第一个数组跑晚了。你的循环还会去比较下一组。
你必须检查index或者在数组的最后设置无限大的最后一个元素 |
|
c*********t 发帖数: 2921 | 8 好像板上过去有人讨论过”数组分段“的问题
“数组分段题”到底问的是什么?谁能给个probelm definition and
description? 在这个版上有没有讨论过的link?
有什么变形?
谢谢! |
|
t*******i 发帖数: 4960 | 9 估计是要处理数组中某字符和另外一个数组的元素不重复,但是和自己树组里的元素重
复的问题。 |
|
h**6 发帖数: 4160 | 10 再用一个哈希表把每次的输出存起来。
对于每个数组2的元素,如果存在于数组1对应的哈希表,而不存在另一个输出哈希表,那么添加到哈希表中并输出。 |
|
b******g 发帖数: 1721 | 11 那我就抛砖引玉了,针对3个数的。
1. 两个for-loops得到任意2个数的和,存在一个临时数组,tmp1. O(n^2)
2. sort (tmp1). O(nlogn)如果merge sort.
3. 再扫一遍原来数组,对于每个元素,a, search(-a) 在sorted tmp1. O(nlogn)
所以,O(n^2).
自我感觉,我们必须对所以pair的数进行判断,所以这就是最优化的算法。 |
|
f*********i 发帖数: 197 | 12 求递增二纬数组,就是排列按行递增,按列也递增的数组(m*n)的第k大的数。
请问有没有比较好的解法。 |
|
p*****2 发帖数: 21240 | 13 Hashtable也行
求两个数组的union 和intersection的时候,如果数组里面有重复的数,在怎么处理?
比如 a[] = {3 2 5 7 8 5 6 5 9}
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
|
f*********i 发帖数: 197 | 14 解法应该是构造一个size 为 k的heap,时间复杂度是O(nlgk)但是有一点我想问大家,
你们是如何判断当前heap最顶端的数是属于哪个数组的呢。用hash的话会有两个key相
同的问题,一个个和数组的数比较的话那就太花时间了。
请问有没有比较好的方法判断。 |
|
|
z******t 发帖数: 25 | 16 对于每一个数字,我们是知道shuffle之后的位置的(ai放在2i-1,bi放在2i),比如
a2,应该放在数字第三个位置。
这样就可以设计一个算法:
读取当前的元素,如果它放置位置不对,则把它和占它位置的那个元素替换,直到当前
位置的元素找到为止。
依次对数组每个元素做这个操作直到结束。
因为每次操作就会有一个元素被放到正确的位置上,所以最差情况需要2n-2次操作(假
设数组中有n个a和n个b) |
|
N*****8 发帖数: 253 | 17 给一个unsorted array,求这个数组中最小的元素差,差的定义为abs(a[i]-a[j])
where i != j .
要求O(n)时间,空间无限,数组没有上下限(既不能用radix/counting sort)。
Ex: input = {5, 13, 7, 0, 10, 20, 1, 15, 4, 18}
output = abs(0-1) = 1
有O(n)算法吗? |
|
c********t 发帖数: 5706 | 18 不用binary O(n^2) 可以输出结果数组。
用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法? |
|
c********t 发帖数: 5706 | 19 不用binary O(n^2) 可以输出结果数组。
用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法? |
|
l*******b 发帖数: 2586 | 20 想输出那个序列得要有一个数组记录每个数值在数列中之前的那个值,所以要多开一个
数组记录这个信息吧.
每次用binary search push进去一个之后那个数之前的一个数就是这个. 写得太烂了,
有空重写一下.
class Solution {
private:
vector s;
vector pre;
int push(int k) {
if(s.empty()){
s.push_back(k);
return -1;
}
if(k >= s.back()){
s.push_back(k);
return s[s.size()-2];
}
int l = 0, r = s.size()-1, mid;
while(l < r)
... 阅读全帖 |
|
t****a 发帖数: 1212 | 21 我把它当二维DP做了,clojure程序和结果如下
(def divide-3-sub
(memoize
(fn [s1 s2 [x & xs]]
(cond (and (zero? s1) (zero? s2)) ['() '() (cons x xs)]
(or (< s1 0) (< s2 0) (empty? xs)) nil
:else (if-let [d1 (divide-3-sub (- s1 x) s2 xs)]
(assoc d1 0 (cons x (first d1)))
(if-let [d2 (divide-3-sub s1 (- s2 x) xs)]
(assoc d2 1 (cons x (second d2)))
(if-let [d3 (divide-3-sub s1 s2 xs)]
... 阅读全帖 |
|
i*****k 发帖数: 102 | 22 一个整型int **p指向一个二维数组的首地址,请问如何知道这个数组的行数和列数?
谢谢~~ |
|
Y**Y 发帖数: 66 | 23 子数组要求连续吧?
两个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 发帖数: 120 | 24 大侠们恕我愚钝,partition完了呢?剩下如何处理正整数部分呢?也就是_inner_min_
set(a+i, n-i, k)如何实现?
比如{5, 1, 4}, target = 8, 因为partition的话就是不要求子数组连续,这时候要排
序吗? |
|
b******7 发帖数: 92 | 25 数组作参数要带上长度
void func(int a[],size_t len)
c/c++不能直接用参数传递数组,而将其转化为指针传递
上面的定义等价于void func(int * a,size_t len)
测试如下的case就可知道
void func(int a[], size_t len)
{
cout<
}
int main()
{
int a[] = {1,2};
cout<
func(a,sizeof(a)/sizeof(int));
return 0;
} |
|
h********m 发帖数: 116 | 26 看网上例子好像用数组多阿,但是觉得数组不太直观阿,而且也不容易扩展。但是为啥
的确很少看到用tree的呢? |
|
f****e 发帖数: 222 | 27 如果把这个数组看成有向图的一个表示方法,那么就是用DFS来找最大环,
每个数组元素的值都不同 是一个很强的条件,楼主没有明确说明这个条件是否给了,
没有给的话就要处理多点指向一点的问题。 |
|
f****e 发帖数: 222 | 28 如果把这个数组看成有向图的一个表示方法,那么就是用DFS来找最大环,
每个数组元素的值都不同 是一个很强的条件,楼主没有明确说明这个条件是否给了,
没有给的话就要处理多点指向一点的问题。 |
|
s********x 发帖数: 914 | 29 那个要additional space,而且binary search 在一个数组小另一个数组大的情况下很
快很多 |
|
m*****n 发帖数: 2152 | 30 又是国旗那道题的变种。
这种题不是有标准解法了吗?
O(M*N) + O(M*Log(M)) + O(M)
N是数组的个数,M是数组的长度。 |
|
v********o 发帖数: 67 | 31 求教哪个国旗题?
又是国旗那道题的变种。这种题不是有标准解法了吗?O(M*N) O(M*Log(M)) O(M)N
是数组的个数,M是数组的长度。 |
|
c****a 发帖数: 50 | 32 比如leetcode interleaving String 即可以二维,也可以一维数组,感觉二维好写一些 |
|
|
d*******l 发帖数: 338 | 34 数组有n个元素的话,m可能的取值只能是0到n,把空间划分成n+2个区间统计一下原数
组落在各个区间的元素个数就能依次尝试了 |
|
x*******9 发帖数: 138 | 35 二分 + 快速划分
平均情况下是O(n)的,即每次都能平分数组。复杂度为O(n) + O(1/2 * n) + O(1/4 *
n)... => O(n)
最差情况是O(n * 2),类似于快排的最差情况。 |
|
s*****4 发帖数: 2 | 36 这个是h-index吧,我记得好像是可以O(N)的,存个数组 |
|
d****n 发帖数: 397 | 37 贴一个python 代码。 这个有点像quick sort里面的deterministic nlgn 算法。重点
是将rank r按两个数组长度分配。
然后在舍弃两个数组其中一个的左边一段。
class Solution:
# @return a float
def findMedianSortedArrays(self, A, B):
m = len(A)
n = len(B)
i = 0
j = m - 1
s = 0
t = n - 1
if (m + n) % 2 == 0:
r1 = (m + n) / 2
r2 = r1 + 1
median = (self.findRankr(A, B, i, j, s, t, r1) + self.findRankr(
A, B, i, j, s, t, r2)) / 2.0
else:
r1 = (... 阅读全帖 |
|
k****r 发帖数: 807 | 38 有一个数组,数组里元素先递增再递减再递增,然后给一个element, 返回该element
的index或者-1, input : [2,3,5,7,-3,-2,-1,4] element:-3
160;返回4。
有人会做吗?谢 |
|
发帖数: 1 | 39 只要两个数组长度一样,那么都从小到大sort一遍,但是要记住原来两个数组的
entries是怎么对应的,比如sort后A组的第0个数是从原来第几个位置移动过来的,B组
的第0个数是从原来第几个数移动过来的。
比如A组第0个数是从原本第5个entry移动过来的,B组排序后的第0个数是从原本第3个
entry移动过来的。那么你需要做的事,就是把B组原本第3个entry的数移动到第5个。
以此类推。
如果不对,那就见笑了 |
|
d********e 发帖数: 321 | 40 上周被问到一个计算 某正整数的比特位, 比如 3 有2个 比特位,我给秒了
然后被追问,如果输入是一个byte[] array,长度为n,问如何计算数组里全部的比特
位?我说挨个数,然后自然是 O(8n),但是面试小哥说要更快的算法,也就是降低常数
项8,我想不出来了,请问有啥好办法?
我记得lc里有一个是数 1 ... n的连续整数的比特位,但是这题是给的byte[]数组 |
|
f*****y 发帖数: 1997 | 41 【 以下文字转载自 Programming 讨论区 】
发信人: fireicy (Light be with you.), 信区: Programming
标 题: 新手问一个多维数组传递给函数的问题
发信站: BBS 未名空间站 (Wed Dec 5 22:17:50 2012, 美东)
请大家看看我的new和delete用的对么? 传给函数的时候,是传指针还是数组名呢?
void main()
{
double **** g;
g = new double *** [m_ydimension];
for(i=0; i< m_ydimension; i++)
{
g[i] = new double ** [m_xdimension];
for (j=0; j< m_xdimension; j++)
{
g[i][j]= new double * [m_zdimension];
for (k=0; k
... 阅读全帖 |
|
q*******i 发帖数: 353 | 42 我遇到的问题是把数组作为参数传递给函数,在函数中数组值被修改同时原来的值也被
修改,有什么办法能让函数中值被修改但是原值不被修改。谢谢
b |
|
q*******i 发帖数: 353 | 43 我遇到的问题是把数组作为参数传递给函数,在函数中数组值被修改同时原来的值也被
修改,有什么办法能让函数中值被修改但是原值不被修改。谢谢 |
|
q*******i 发帖数: 353 | 44 就调用一次啊,在函数外先 arraycopy(b,a)。然后把数组b传递给函数,在函数中
修改数组b的值同时,a的值也被修改,我想达到只在函数中修改b的值,a的值不变,除
了你刚才说的办法,还有没有其他更高效的办法? |
|
R*******n 发帖数: 162 | 45 标准做法是 各个数组的头一个元素都拿出来建一个heap
O(log(L)N), L 是数组数, N是所有元素的数目
的。 |
|
t********k 发帖数: 808 | 46 比如
我已经定义了一个Typ1的对象类型
我想在Typ2对象类型中定义一个成员为Typ1的数组属性?
在Typ2中
用
Type Typ1List IS TABLE OF Typ1;
typ1List Typ1List; -----------------这样不行
用
typ1List TABLE OF Typ1
也不行
难道不用定义数组类型的属性? |
|
m**********e 发帖数: 19 | 47 我查来查去,Array.Sort只支持一维数组,至多是两个一维数组.
如果我的sort需要用到primary key 和 secondary key, 好象就没有办法了. |
|
j*******s 发帖数: 81 | 48 java里开辟数组的时候,好像有很多额外的开销啊。
[1000][1] 比 [1][1000] 需要多花费N倍的内存,是不是因为 [1000][1]中开辟
1000个一维数组的时候的额外开销呢?
多谢指点! |
|
l******0 发帖数: 244 | 49 “如果有很长一段时间不reference这个数组了,貌似操作系统自动的把内存腾出来了
,也就是,这个数组进了disk 缓存区了”
这个你是怎么判断出来的? |
|
o******r 发帖数: 259 | 50 问题出在释放数组空间的时候
有一个class A;
申请内存
A *pA = new A[10];
释放时
delete[] pA;
debug version就会报错
release version没有报错
改成指针
A *ppA = new A*[10];
for (int i = 0; i<10; i++) ppA[i] = new A;
释放时
for (i = 0; i<10; i++) delete ppA[i];
delete[] ppA;
就没错
有谁知道两者区别?跟数组分配有关吗?
用后面那种方式写的时候比较罗嗦,用前面这种方式写的在程序负责以后在release version
下也报错了,改起来地方太多了 |
|