Y********f
发帖数: 410 | 1 刚做了这道题，leetcode上为了不调用find kth elments两次写了一个比较复杂的。我
写了一个稍微简单点的，实际上也是基于find kth element.
double median2Array(int* arrA, int lenA, int* arrB, int lenB, int k, int
isEven)
{
if (lenA == 0)
return isEven ? (arrB[k-1] + arrB[k]) / 2.0 : arrB[k-1];
else if (lenB == 0)
return isEven ? (arrA[k-1] + arrA[k]) / 2.0 : arrA[k-1];
else if (k == 1)
{
vector vect(min(2, lenA) + min(2, lenB));
copy(arrA, arrA + min(2, lenA), vect.begin());
copy(ar... 阅读全帖 |
|
g*****e
发帖数: 282 | 2 k sorted array merge有很多解法，根据各array长短的情况各种算法效率各异。大家
一般还是选择建个k heap而不是每次选两个array merge吧？那样的话写个heap实现还
是挺麻烦的。能假设有现成的min heap或者max heap可以调用么？哪位朋友实际面试里
碰到过的讲讲吧。多谢！ |
|
r*****e
发帖数: 146 | 3 We have K sorted array, A1, A2, A3,... Ak, the corresponding size for array
Ai is Ni, in total we have N numbers, N = N1 + N2 + ...+Nk. How to find the
median among N numbers in O(K (logN)^2) ? |
|
c********t
发帖数: 5706 | 4 quicksort? 与求kth in two sorted array 一样吧？ |
|
c********t
发帖数: 5706 | 5 quicksort? 与求kth in two sorted array 一样吧？ |
|
|
d******e
发帖数: 164 | 7 请问怎么以标题顺序sort问题啊。。。做了一半，现在没顺序了。。。
最好OJ有个单独的Link。。。Thanks! |
|
|
c***s
发帖数: 192 | 9 这个就是跟 kth of two sorted array一样的吗？
我刚被面到过，然后我告诉面试官我做过这道题，
他先让我讲了一下思路，然后写了特殊情况就过了。
折半比较就可以了啊。 |
|
c***s
发帖数: 192 | 10 如果找第k个小的值（数组从小到大排列）的话，
只要砍掉左边的就可以了，（右边的不用管）。
下面是从A数组的pa开始和B数组的pb开始中 找第k个最小的值。
int findMedian(int[] A, int pa, int B[], int pb, int k) {
int i, j = 0, n = k / 2, qa = A.length, qb = B.length;
if(k <= 3) {
int[] C = new int[(k + 1) * 2];
for(i = pa; i < qa && i <= pa + k; i++) C[j++] = A[i];
for(i = pb; i < qb && i <= pb + k; i++) C[j++] = B[i];
for(i = j; i < (k + 1) * 2; i++) C[i] = Integer.MAX_VALUE;
Arrays.sort(C);
return(C[k]);
}
... 阅读全帖 |
|
|
L****Y
发帖数: 355 | 12 sort 1 million floating point numbers
any ideas？ 大牛们 |
|
n****r
发帖数: 120 | 13 An operation "swap" means removing an element from the array and appending
it at the back of the same array. Find the minimum number of "swaps" needed
to sort that array.
Eg :- 3124
Output: 2 (3124->1243->1234) |
|
|
h***i
发帖数: 1970 | 15 inversions and merge sort. |
|
z****p
发帖数: 18 | 16 I think backtou has already given the answer. Let me elaborate it:
-Naive approach: find the smallest element in the array, "swap" it to the
tail; then find the 2nd smallest element, "swap" it to the tail; ...
-Improvement, if the first K elements are already in an increasing order in
the original array, then in the naive approach, we can simply start with the
K+1-th smallest element
-So the minimal number of "swaps" is N-K, where K is the longest prefix of
the sorted array that are already in t... 阅读全帖 |
|
g********r
发帖数: 58 | 17 An operation "swap" means removing an element from the array and appending
it at the back of the same array. Find the minimum number of "swaps" needed
to sort that array.
Eg :- 3124
Output: 2 (3124->1243->1234)
看到版上有人讨论这道题， 总觉得应该有更优解。 而且假设 数字是从 1-n 有些牵强
。昨天想到了一个解法，今天又稍稍更新了一下。个人的理解 大家看看有没有错。谢
谢！
1. 如果数组长度是n，最多就需要swap n－1次，就是每个元素 最多只需要swap一次。
我们并不需要关心哪个先哪个后swap。 那么 我们就一个一个元素的判断那些需要swap。
2. 首先 如果 给定元素的右边 有更小的值，这个元素就需要swap， 比如上例中的3
3. 然后，再看 剩下的没有swap的元素，如果值比 “在第二步中需要swap的所有元素
的最小值” 大， 那这个元素 就需要 sw... 阅读全帖 |
|
b*******e
发帖数: 217 | 18 works for 3124 too
(1) push 3 into stack
(2) find 1 is a local min
(3) pop out 3 from the stack and insert it to the back of the array
(4) now array becomes 1243 and the pointer to the array go to 0.
(5) now push 124 into stack. find 3 is a local min
(6) pop out 4 (don't pop out 12 since they are smalelr than 3).
(7) insert 4 to the end of the array.
(8) sorted ast 1234.
The number of swap can be decidied during process above. anyone can help to
analyze the time complexity? |
|
g********r
发帖数: 58 | 19 真不知道 您在说什么
first round (1) 32 needs swap then step = 2
second round (2) 4 need to swap then step += 1
so step = 3
why we care about how to sort? |
|
|
E****U
发帖数: 59 | 21 Remove Duplicates from Sorted Array II:
class Solution {
public:
int removeDuplicatesII(int A[], int n) {
if (!A || n <= 0) return 0;
int dsc = 1;
int dupCount = 0;
for (int i = 1; i < n; ++i)
{
if (A[i] != A[i-1])
{
A[dsc++] = A[i];
dupCount = 0;
}
else
{
++dupCount;
if (dupCount < 2)
{
A[dsc... 阅读全帖 |
|
c********t
发帖数: 5706 | 22 发现自己O(n^2)的sort都没写过啊，面试会考？ |
|
c********t
发帖数: 5706 | 23 可能性不大。
我前几天写array in-place merge sort差点吐血，最后发现还不是O(nlgn),真悲催。 |
|
c*******r
发帖数: 309 | 24 还是没搞懂。如果是N个sorted array...是应该建大小为k的max heap么？ 然后每个
array的指针往heap里insert，都和root比，如果比root大的话就更换 |
|
c*******r
发帖数: 309 | 25 还是没搞懂。如果是N个sorted array...是应该建大小为k的max heap么？ 然后每个
array的指针往heap里insert，都和root比，如果比root大的话就更换 |
|
c*******r
发帖数: 309 | 26 电面改了好几次最后才给了个Linked List 版本的bubble sort..... |
|
|
G****A
发帖数: 4160 | 28 我觉得最佳方案是拷贝成array，然后quick sort. 但你要能解释出为什么。 |
|
|
s********x
发帖数: 914 | 30 是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。 |
|
f******k
发帖数: 43 | 31 多线程来做无非就是复杂度除以线程数，不会改变复杂度级别吧，还是nlog(n)吧，除非
生成的线程数是和n相关的
是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。 |
|
x*********w
发帖数: 533 | 32 为什么quick sort partition 在中间优于在1/3的位置？
换一个角度说，为什么
T(n) = n + T(n/2) + T(n/2)
优于
T(n) = n + T(n/3) + T(2n/3) |
|
t*****s
发帖数: 416 | 33 这题不难，只是merge sort的一步迭代过程而已。我一开始还想复杂了想从两个数组的
两头开始往中间找。 |
|
D****6
发帖数: 278 | 34 merge一部分，放进一个file,merge下一部分，append进同一个file,一直到完，那个
file不就是sorted吗。 |
|
D****6
发帖数: 278 | 35 一个，但不是array,是write到disk里的一个file. 你是说external merge sort吧？ |
|
i****y
发帖数: 84 | 36 你用了min heap。。lz意思是不用min heap直接merge sort？ |
|
n*******k
发帖数: 100 | 37 就老老实实的取2个文件f1，f2（比如整数）的头元素放在变量v1，v2里面，较小的值
写入磁盘结果文件，（判断读完与否，feof() ）
while(f1未读完且f2也未读完)
如果v1 <= v2， fwrite(&v1,4Byte,1,res_file)，从f1读取下一个数；
否则fwrite(&v2,4Byte,1,res_file),从f2读取下一个数。
if (f1读完，f2没被读完)
flush f2剩余元素进入res_file
if (f2读完，f1没被读完)
flush f1剩余元素进入res_file
这样不就行了吗？
fread/fwrite可以利用文件缓冲区。如果自己想偷懒，不想切文件，定义和管理文件缓
冲区，直
接这样用就可以了。出来的文件就是globally sorted。 |
|
p*****3
发帖数: 488 | 38
以index为标准做的二分，two sorted array 找第k大的。
（另外为了避免被版上大牛喷我发誓这个是N久以前的code,俺现在不做题一心一意学
java） |
|
|
|
l********7
发帖数: 40 | 41 merge sort不复杂吧，都不用额外分配空间 |
|
|
m*******n
发帖数: 103 | 43 偶没有看过leetcode，楼上几位都用merge sort是有什么原因吗？ |
|
s**x
发帖数: 7506 | 44 better split into more functions like geeksforgeeks
http://www.geeksforgeeks.org/merge-sort-for-linked-list/
also, I do not think we really need to split the list to half and half first
, need to a similar way for converting single linked list to BST,
from bottom up, move the list accordingly.
still nlogn though. |
|
|
|
y*****3
发帖数: 451 | 47 这倒无妨，merge sort也可以写成 while loop的 |
|
C*******n
发帖数: 24 | 48 Find the Kth smallest element in 2 sorted
array. so if you have 2 arrays&#
160;[1, 5, 9, 15, 20, 34] and [2, 6,
8, 10, 11, 19] and k = 5, the&
#160;answer is 8. Basically whats the
5th smallest number in the 2 arrays
combined.
Any ideas? |
|
e******g
发帖数: 51 | 49
sorted
6,
the&
假设数组是A[n], B[m], n > m
if k > m + n return -1
else 对A[1:min(k,n)] 和 B[1:min(k,m)] 递归二分查找 |
|
w**7
发帖数: 22 | 50 find median of two sorted array |
|
