I**A
发帖数: 2345 | 1 Given a sorted list of N integers that has been rotated an unknown number of
positions, e.g., 15 36 1 7 12 13 14。 design an lg(n) algorithm to
determine if a given integer is in the list
你们谁写过code，可否share share? 我比较着比较着就乱了。。 |
|
j**l
发帖数: 2911 | 2 如果没有重复元素
假定当前搜索区间开始的下标是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
} |
|
j**l
发帖数: 2911 | 3 二分法找pivot (reset point)的下标, 假定没有重复元素
int findResetPoint(int s[], int start, int end)
{
if (s == NULL || start < 0 || end < 0 || start > end)
return -1;
// At least three elements in the range
while (end - start > 1)
{
// sorted case, no rotation
if (s[start] < s[end])
return start;
int mid = (start + end) / 2;
if (s[mid] < s[mid - 1])
return mid;
if (s[start] < s[mid])
start = mid + 1;
els |
|
y*********e
发帖数: 518 | 4 贴一贴我的Java代码，希望有帮助！
/*
* Given a sorted array, which is rightwards rotated X steps.
* Find X.
*/
public static int findRotate(int[] array) {
return findRotate(array, 0, array.length - 1);
}
/*
* Approach:
*
* Find the first element pair x, y such that x > y.
* Then the index of x is the answer.
*
* 1. Take the median value. If it is greater than its previous
* element, then the index of the median is what we look for.
|
|
s*********t
发帖数: 1663 | 5 read the signiture of sort..
only thing worth mention here is: v + 1000 correspond to v's end() since v h
as a type of int. |
|
h**6
发帖数: 4160 | 6 说实话，这理由还真不好说，一直都是这么用的。
如果v是一个vector，那么应该用 std::sort(v.begin(),v.end()) 进行排序。
作为数组，数组名 v 同时也表示第一个元素的地址，相当于 v.begin()，而 v+1000 则是最后一个元素之后的地址，相当于 v.end() |
|
b********e
发帖数: 693 | 7 这个怎么做到? 如果是32位integer的话 如果是做redix sort的话,是不是就可以O(N)了 |
|
b********e
发帖数: 693 | 8 radix sort应该能实现吧
我知道hash是能实现的 |
|
|
V*****i
发帖数: 92 | 9 在merge sort中，需要设一个sentinel，大家都是用什么的？在现实编程中，你一般已
经知道了值的范围，所以随便设个很大的数就可以了，但总觉得这在面试中不够严谨，
大家是怎么办的？我试过numerical_limit<>::max()，但发觉很慢。
类似的是，在hash table open addressing算法中，需要设nil和delete，大家是设成
什么的？ |
|
d**e
发帖数: 6098 | 10 merge sort, sentinel? 为什么？ |
|
c******n
发帖数: 4965 | 11 A[0] .... A[n]
kind of "sort" it so that
A[i] < A[j] where j> i+K, and i in [0, n-K]
I remember working it out before, but forgot |
|
s*******e
发帖数: 93 | 12 如果是j= i + k 就不难了。
直接把A 分成 k 个 subarray
第一个是 A[0], A[0+k], A[0+2k]...
第二个是 A[1], A[1+k], A[1+2k]...
..
最后是 A[k-1], A[2k-1]..
然后sort 每一个subarray
应该是 n log(n/k)
如果是A[i] < A[j] where j> i+K 好像还有点难 |
|
f***g
发帖数: 214 | 13 相似题目：两个sorted Array找中数。 |
|
k****n
发帖数: 8684 | 14 not to sort a list of string
谢谢大牛解答。 |
|
s*******n
发帖数: 344 | 15 大文件用 external sorting来进行排序
先分块排序，然后merge.
但是merge这个环节怎么除里？内存不够啊还是 如何 merge?
多谢解答 |
|
g***s
发帖数: 3811 | 16 Even if it is not sorted, the finding median of all (k*n) item only needs
O(k*n) |
|
g***s
发帖数: 3811 | 17 1. put all number into one array, size = k*n O(k*n)
2. find the median of the array O(k*n)
I think LZ is asking for a better solution since the above method doesn't
care if it is sorted or not in the k arrays.
【 在 lolhaha (haha) 的大作中提到: 】 |
|
a******7
发帖数: 106 | 18 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******7
发帖数: 1728 | 19 external sorting的最后一部 merge的时候，是不是要消耗很多I/O
因为内存就那么大。之能不断的读写 这要以高IO为代价 我理解的对不对？xi谢谢 |
|
h*****g
发帖数: 312 | 20 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类似的方法，该咋做呢？ |
|
|
s******d
发帖数: 61 | 22 我查了下counting sort, 用另外的数组来存原数组元素排序后的位置, 但是只单个数
组的排序, 不清楚怎么应用到这里? |
|
|
|
f****4
发帖数: 1359 | 25 原帖：http://www.mitbbs.com/article_t/Programming/31198701.html
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
有O(n)的解么？怎么转化成杨矩啊？
谢谢 |
|
f****4
发帖数: 1359 | 26 原帖：http://www.mitbbs.com/article_t/Programming/31198701.html
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
有O(n)的解么？怎么转化成杨矩啊？
谢谢 |
|
k****n
发帖数: 369 | 27 最简单的办法是坐n-way merge sort |
|
|
|
r****t
发帖数: 10904 | 30 一般 sort 方法都接受一个可定制的 compare function |
|
i******e
发帖数: 273 | 31 SortDESC 是function object 也叫functor. 是sort algorithm的一个参数 |
|
G**********s
发帖数: 70 | 32 有没有人在 A/M/G onsite 时候，遇到过以下知识点相关的题呢？
234tree
RBtree
splayTree
nWayMergeSort(External sort)
犹豫是否要花时间把这些也复习。xiexie! |
|
|
f*******n
发帖数: 12623 | 34 的确是nlogk。O(1)可以拿到top element，但是要remove它，还是要O(log k)。
假如k=n，那按照他说的就可以用这个方法O(n)去sort一个unsorted的array了。 |
|
w****o
发帖数: 2260 | 35 在这个班上看见过，但是具体的题的描述我不记得了。
好像是给一个 sorted array of integers,给一个value,找这个value.
可是有可能这个value在数组里出现多次。
到底这个题是要找出value在数组里出现的次数？还是要找出一个表示index的范围？
比如数组 a=[1 2 3 4 6 6 6 9 10], value=6,
是要求返回3 （6出现的次数）， 还是要返回{4, 6}? 因为a[4] = 6, a[6] =6?
到底面试的时候，问到的是哪种情况？
谢谢！ |
|
k*******r
发帖数: 355 | 36 求两个sorted array合并后的median这题，我知道网上有答案可以在log(min(m,n))时间复杂度内做完，就是不断比较两个array各自的中位数缩小范围，但具体写代码也太琐碎了吧。
主要是数组元素为奇数和偶数时，中位数定义不同，对一短一长两个数组，就得分别考虑奇奇，奇偶，偶奇，偶偶4种情况，每种里面比较中位数大小又是3种可能....
有没有比较clean的代码，在30行代码左右能搞定这题的。（我觉得太长的代码，白板也很难写对阿） |
|
n*p
发帖数: 298 | 37 就是有millions of words
要进行sorting
而且是multi-core或者MPI
想用hash table加linked list
有没有相关的C代码 |
|
j********x
发帖数: 2330 | 38 假设是1千万的单词
每个单词平均长度为7
才70Mb。。。
直接上stl sort都搞的定
非要弄多线程 mpi，那也是直截了当的事情。。 |
|
s*****n
发帖数: 162 | 39 n个sorted arrays，每个有n元素，求第k大的数，江湖传闻有paper给出了O(n）的解，
不过解法应该很复杂，因为这题反复讨论过，至今也没有见到O(n)的详解。退求其次，
有O(n log n)的解法，用到median of medians和weighted median。这个解法比用堆的
O(k log n)算法，有更好的时间复杂度，因为in the worst case, k是O(n^2)。但这个
解法在面试中，要写出code来，估计也不太可能。 |
|
|
w****x
发帖数: 2483 | 41 //Print strings with certain prefix in a sorted string array
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2);
void PrintComPrefix(const char* strs[], int n, const char* szPre)
{
assert(strs && szPre && n > 0);
const char* p = szPre;
int nIndex1 = 0;
int nIndex2 = n-1;
while (*p != 0 && nIndex1 >= 0)
{
GetIndex(strs, nIndex1, nIndex2, *p, p-szPre, nIndex1, nIndex2);
p++;
}
if (nIndex1 >= 0 ... 阅读全帖 |
|
w****x
发帖数: 2483 | 42
heap sort稳定nlogn, 但是不是stable的, 所有存在swap的排序算法都不是稳定的 |
|
|
|
a*******y
发帖数: 1040 | 45 sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
binary search的变种
我感觉这个不是O（logn）啊
code是发现repeat次数的
int binarySearch(char* charset, int start, int end, char target)
{
if (charset == NULL) return 0;
if (start == end)
{
if (charset[start] == target) return 1;
else return 0;
}
int mid = start + (end-start)/2;
int left = 0, right = 0;
left = binarySearch(cha... 阅读全帖 |
|
S**I
发帖数: 15689 | 46 Read the source code of equal_range in a C++ implementation. In both VC and
GCC, implementation of equal_range is based on lower_bound and upper_bound,
both of which have log(n) complexity if the range to be searched is a sorted
array. So equal_range has complexity 2log(n). |
|
c****g
发帖数: 85 | 47 code is here. Please comment on this.
平时不用Java的，发现做题用Java比C++方便（没指针，有更多的函数，呵呵）
另外，函数返回一个boolean（有可能数组根本没有k这么多elements）和一个number。
查了网，说可以用一个临时类，来返回其对象。我嫌麻烦，用了一个输入变量来返回
number值。但是直接不能返回，所以用了int[]。觉得有点awkward。不知你们怎么处理？
package leetcode;
import java.util.*;
public class kthSmallestElementTwoSortedArrays_Ver2 {
public static void main(String[] str)
{
// build two sorted arrays:
int[] A = {1,3,4,4, 7,9,10, 13, 15, 19, 20, 33};
int[] B = {2,5,5,6,12 };
// ... 阅读全帖 |
|
l****c
发帖数: 782 | 48 If the numbers of two sorted array are huge enough, can I write the code as
followed?
int returnKint(int* s1, int* s2, int start1, int start2, int k){
if (k == 1)
return s1[start1]
else {
if (s1[start1+k/2-1] < s2[start2+k/2-1])
return returnKint(s1, s2, start1+k/2, start2, k-k/2);
else
return returnKint(s1, s2, start1, start2+k/2, k-k/2);
}
} |
|
g****y
发帖数: 240 | 49 贴个python版的
def findk(alist, blist, k):
"""Given two sorted array, find kth minimum element"""
m = len(alist)
n = len(blist)
assert (k <= m + n)
if m == 0:
return blist[k - 1]
elif n == 0:
return alist[k - 1]
if k == 1:
return min(alist[0], blist[0])
# divide k into two even parts as much as possible
ai = min(k // 2, m)
bi = k - ai
if bi > n:
bi = n
ai = k - bi
if alist[ai - 1] == blist[... 阅读全帖 |
|
Y********f
发帖数: 410 | 50 刚做了这道题，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... 阅读全帖 |
|
