g*******y
发帖数: 1930 | 1 你在哪儿看的，某论坛某帖子里面某个普通老美/老印的回复？直接无视之！
我是看不出他这个算法是怎么做到O(N)+O(1)的
O(n)+O(1)的解法是有人发过paper的，哪有这么轻松的。好歹也得整些数论在里面
this step and [] is what has been moved from last step. The array itself is
used as storage and two pointers (one for L and one for N) are required to
determine what to move next. L means "letter line" and N is "number line" (
what is moved). |
|
|
l***i
发帖数: 1309 | 3 Given an int array of positive and negative numbers, rearrange it in O(1)
extra space such that all positive numbers are on the left and all negative
numbers are on the right, and the relative order of positive numbers, and
the relative order of the negative numbers are the same as in the input.
Can it be done in O(n)? |
|
|
w**********8
发帖数: 121 | 5 Given three sorted arrays, A, B, C, each of length n (assume odd), with all
3n elements distinct, find the median of the 3n elements.
O(n) time is easy to do. Is there an O(logn) time algorithm? |
|
w**********8
发帖数: 121 | 6 I am thinking this way.
let n = 2m +1;
* Let three median are Am, Bm, Cm
* compare them, let Am < Bm < Cm
* get rid of 0 ... m in A, and m ... n-1 in C
* for the rest of arrays, repeat the 3 steps above.
each time, we get rid of 2/6 of the rest numbers, i.e. T(n) = C+T(2n/3). This
is not O(log(n)) as well.
That's the best I can gave. Any other ideas? |
|
r****c
发帖数: 2585 | 7 it is not absolute right,
since the number of elements are not same for three arrays, your method does
not work well in degraded case
This |
|
h********0
发帖数: 440 | 8 Thought of a naive change, but the code is not pretty.
Basically, this recursion is a problem for partitions with odd numbers.
We can do a preprocess after partition.
1. if the two parts contain even number,no change.
2. if the two parts contain odd number,
do the following ugly exchange
part 1: [p...r]
part 2: [r+1 ...q]
logically:
exchange the right half of part 1 and the left half of part 2
move the middle element of part 1 to array[r]
move the middle element of part |
|
m******9
发帖数: 968 | 9 这个可以log2k找到
你从array 1中取前k个数, 从array2中也取前k个数. 然后对取出来的这2个子数组, 找
median, 就是整个array1和array2的kth min了 |
|
|
g********n
发帖数: 127 | 11 Then go to the second array to find k+r elements (in which r = k - length_
1st_array). |
|
C*Y
发帖数: 736 | 12 How? And is linked list-based implementation better than array-based
implementation? |
|
h******3
发帖数: 351 | 13 I think the idea is correct.
Also, think about special cases such as the array length is less than K. |
|
s*****n
发帖数: 956 | 14 开始问怎么计算这颗树有多少个节点。 这个就是简单递归。
后来问怎么把它存到一个sorted array.
void storeIntoSortedArray(Node* root, int* p)
{
//允许就在里面给 p allocate memory
}
怎么弄啊？有没有遍历一遍就能存好的方法？ |
|
c*r
发帖数: 9 | 15 比如从以下array找3.有好的算法吗？
［2，2，2，3，2，2，2，2，2，2，2，2］ |
|
c**y
发帖数: 172 | 16 函数声明如下
void function1（const char *a) {
...
...
return;
}
如何能在函数function1中访问a呢？我只想到用strcpy的方法把a复制到另外一个char
array中。有没有什么办法直接访问a，而不使用额外的内存？ |
|
j**l
发帖数: 2911 | 17 如果没有重复元素
假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
if (s > e)
查找失败返回;
m = (s + e) / 2;
if (x == A[m] || x == A[s] || x == A[e])
查找成功返回;
if (A[s] <= A[m])
{
if (x > A[s] && x < A[m]
在区间[s+1, m-1]继续找
else
在区间[m+1, e-1]继续找
}
else if (A[m] <= A[e])
{
if (x > A[m] && x < A[e]
在区间[m+1, e-1]继续找
else
在区间[s+1, m-1]继续找
}
else
{
// This is not possible if the original array is circular sorted
} |
|
K******g
发帖数: 1870 | 18 有个一个N*N的array，里面的元素是pos或者neg的整数，求最大的一个所有元素和最大
subarray。 |
|
I**A
发帖数: 2345 | 19 N*N是个matrix
看过求array的最大subarray
木见过怎么求matrix的subarray，你是说submatrix maybe? |
|
x***y
发帖数: 633 | 20 find a submatrix with the largest sum, similarly to find a subarray with the
largest sum in an array... |
|
Z*****Z
发帖数: 723 | 21 a linked list of array objects? |
|
h*****n
发帖数: 209 | 22 a linked list of char array? |
|
j*****g
发帖数: 223 | 23 nope. the array elements are random, not sorted, binary search doesn't fit
here. |
|
j*****g
发帖数: 223 | 24 有点意思，但你的optimization只在array的尾巴上，isn't it a bit too little too
late?
] |
|
l*****a
发帖数: 14598 | 25 比较array1[k/2] array2[k/2]
if = ,return
if array1[k/2]>array2[k/2] , array2[0..k/2]are definitely in the k smallest
then choose k/2 smallest
from array1[0..len1-1-k/2] array2[k/2+1..len2-1]
...
pay attention the boundary of the array. |
|
|
f***g
发帖数: 214 | 27 相似题目：两个sorted Array找中数。 |
|
l********y
发帖数: 1327 | 28 median of an array of ints, 请问这题的经典回答是什么？谢谢 |
|
d********w
发帖数: 363 | 29 First, we can consider 2 numbers, which is O(n) time. We can use 2 two
pointers to process the sorted array or use hashtable to find whether T-cur
in it.
If k = 3, the running time is O(n^2), wiki describes the algorithm http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
"When the integers are in the range [−u ... u], 3SUM can be solved in
time O(n + u lg u) by representing S as a bit vector and performing a
convolution using FFT." but it is hard to follow.
How about numb... 阅读全帖 |
|
r*******e
发帖数: 7583 | 30 这个明显不对，举例：
1 2 4 5 6 3 9 7 8
你的算法返回的是 6 3 9 7
能不能直接返回i，还跟这个sub-array的min和max有关 |
|
c**********6
发帖数: 105 | 31 agree
把k个array当作一个用partition algorithm
cheers！！ |
|
|
a******7
发帖数: 106 | 33 the book already assumed each sorting in O(1) time, when the sub-array is
small enough. I don't think we can do better in worst case. On average case,
maybe. |
|
|
h*****g
发帖数: 944 | 35 今天被问到如和在c++里创建a two -dimensional array of string?
我这解说 String hi [20][20];
好像错了，似乎c++不支持这么做，请问应该怎么declare?
char * hi [20][20]好像也不对吧 |
|
w********r
发帖数: 6 | 36 【 以下文字转载自 Java 讨论区 】
发信人: waterwater (huahua), 信区: Java
标 题: 如何用JAVA中的circular array of queue 解决Josephus problem?
发信站: BBS 未名空间站 (Thu Mar 24 00:31:04 2011, 美东)
本人初学JAVA,不知道如何用JAVA解决.
请各位多多指教.
waterwater |
|
h**********d
发帖数: 4313 | 37 定义一个Node class，field里面放同类型的instance varable next，然后自己生成一
个circular array，Node头尾相连就行 |
|
c********1
发帖数: 52 | 38 array如果是sorted 保持两个指针 一个头一个尾往中间移动就行了
为什么不是one iteration as required？ |
|
g**e
发帖数: 6127 | 39 it's one iteration.
I didn't noticed it's a sorted array, so use head & tail pointers and scan
forward/backward. it's better. |
|
s*****y
发帖数: 897 | 40 The array should not be sorted.
Is it? |
|
h*****g
发帖数: 312 | 41 Let’s called array1 as A and array2 as B, each with size m and n.
正常的话，O(m+n)应该可以搞定，但是。。。
if n is very very large, the memory can not hold it.
i) What if elements of array B is stored on disk, and the memory is limited
such that you cannot load all elements into the memory at once?
ii) How will the complexity change in this case? Are there any factors you
need to consider?
iii) How do you change your solution to adapt to this situation?
如果用external sort类似的方法，该咋做呢？ |
|
m**q
发帖数: 189 | 42 How about using B+ tree?
The tree itself will reside in memory, and you can do
a search in the tree for each element in A, locate the
appropriate block range and lock it into memory. That
way you don't need to traverse the whole B array and
thus should be faster, assuming m is relatively small.
limited |
|
j**y
发帖数: 462 | 43 array 5,3,7,5,12,5,5
sum 10
output
5,5
3,7
5,5
5,5
5,5
5,5
5,5
no O(n^2)
Thanks |
|
m********l
发帖数: 4394 | 44
重看了下， 你的问题好像没说清楚
不过试试用Chained Hash了吗？
1) create the hash table.
2) create a link-list node that stores the position of the value
3) put the values inside the hash table. Preferably, during insertion,
you want LIFO
4) loop thru the array again
4.1) get hash[sum-value]
4.2) print if the position of the hash value is greater than current
value's position.
4.3) if position > node->position, continue;
=============
Yes, it's a hack.
why do they test you on procedural stuff when all they teach you in... 阅读全帖 |
|
n**z
发帖数: 155 | 45 Java? Arrays only have a sort function |
|
n**z
发帖数: 155 | 46 static void sort(Object[] a)
Sorts the specified array of objects into ascending order,
according to the natural ordering of its elements. |
|
m**q
发帖数: 189 | 47 Looks like an old question, but failed to find a better solution than O(klg(
m+n)). Any ideas?
The question is quoted from a comment on ihas1337code website
------
1.Two reverse sorted arrays A and B have been given. such that size of A is
m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n It can be done in O(n*n) but i believe it
can be done in a very efficient way. I heard someone say there is a paper
from SODA. I... 阅读全帖 |
|
g*****i
发帖数: 2162 | 48 这个J-Max track array思路很好,但是表现上比hashset会好很多吗?
第二题判断有没有插入过似乎这个J-max就用不上了.
里。
j
+1 |
|
s******d
发帖数: 61 | 49 We have two sorted int arrays
a[] --> size N --> contains N elements
b[] --> size 2N --> contains N elements, and N vacant locations
Write an algorithm of complexity O(n) such that b[] contains elements of a[]
and b[] in ascending order.
merge()能保证复杂度o(n)吗?......sorting还没复习,稀里糊涂的现在==|| |
|
B*******1
发帖数: 2454 | 50 如果允许有重复元素，像这种array 2 1 2 2 2
找1咋办？ |
|
