f*****e
发帖数: 2992 | 1 然后就继续recurse，新的arrays长短就不一定了。 |
|
p*****p
发帖数: 379 | 2 两个array大小一样就好写
或者就先merge起来 |
|
c***s
发帖数: 192 | 3 这个就是跟 kth of two sorted array一样的吗？
我刚被面到过，然后我告诉面试官我做过这道题，
他先让我讲了一下思路，然后写了特殊情况就过了。
折半比较就可以了啊。 |
|
c***s
发帖数: 192 | 4 如果找第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]);
}
... 阅读全帖 |
|
|
r**h
发帖数: 1288 | 6 要是输入是2 1 4 3的话，因为2在1前面，因此
if (array[index] == target)
当target=2时候永远不成立，从而使得minswap = 3，但解是minswap = 2
是我理解错方法了吗 |
|
c********t
发帖数: 5706 | 7 嗯，基本达成共识。
具体怎么解呢？ 先排序并存到另一个array, 再比较原数组得出longest prefix？
time O(nlgn) space O(n)?
in
the
be
). |
|
A***o
发帖数: 358 | 8 May be I am wrong, consider the following ...
Let the unsorted array be V=a_0, a_1, ... a_k, ... a_m
assume min(V)=a_k
'swap' all a_i such that i
Let V_1 = a_0 ... a_(k-1)
w.l.g., assume min(V_1) = a_l
Let V_2 = a_(k+1) ... a_m
w.l.g., assume min(V_2) = a_r
Now scan V_2, 'swap' an a_i (k+1<=i<=m), if
(i) a_i > a_r and i < r; OR
(ii)a_i > a_l
O(n) time, O(1) space? :) |
|
b*******e
发帖数: 217 | 9 starting from the first element to the last element:
if any element after it is smaller than it, swap this element to the enf of
the array
seems n^2 worst case.
needed |
|
|
E****U
发帖数: 59 | 11 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*******r
发帖数: 309 | 12 这题到底具体应该怎么解啊？ 临近面试发现又什么都不会了。。。。
有N个pointer指向N个array的头，然后binary search这N个element然后找到最大的
insert到heap.
time complexity :O(logN*totallength)
或者直接建一个k size maxheap,然后insert所有元素
time complexity : O(logK*totallength) |
|
o****o
发帖数: 23 | 13 既然是sorted（假设是从大到小），就用一个size n的最大堆，每次取出最大的，然后
加入该元素所在数组的后续元素，heapify之后再取，直到取到top K停止。
如果不是sorted，那就得用size k的最小堆，遍历所有array的剩余元素，分别与最小
堆的root比较，大于root就替换root，heapify一下，小于等于就跳过。 |
|
D**********d
发帖数: 849 | 14 到底是 k >> N 还是 N << k?
如果 N array 连头元素的排序也没有，那至少要建个 size k 的 heap 来排头元素啊,
这样要 N*lgk, 剩下还要 k*lgk 找出前k个 |
|
f*********m
发帖数: 726 | 15 大家都讨论过了，这里想再确定一下：
给定m个sorted linked list or array,平绝长度为n。则：
（1）divide conquer:
T(mn)=2T(mn/2)+O(mn) =>T(mn)=mnlog(mn)
（2） minheap:
m(构造Heap）+(mn-m)logm=〉mnlogm
(3)从一个list拿出头元素与其他list的头元素比较：
mn*m。
由此可见（1）和（3）不一定哪个好，决定于m和n的值。m或n很大时（1）比（3）好。
请指教。 |
|
f********1
发帖数: 228 | 16 【 以下文字转载自 Programming 讨论区 】
发信人: falcon8241 (falcon), 信区: Programming
标 题: A weird C programming language--Return a pointer to array
发信站: BBS 未名空间站 (Wed May 29 13:54:54 2013, 美东)
A question I encountered during the interview. Could anyone give me some
idea.
The key issue is I was asked to modify line 500, which is the function
declaration...
Is there a different way to write line 500 which preserves the same
effective prototype? If so, what is it?
Line in file
Code:
30 int * someIDs, theFirst,... 阅读全帖 |
|
c****9
发帖数: 164 | 17 Just change return type to integer array. int[]? which will return a copy
not a pointer. |
|
c**y
发帖数: 172 | 18 这个code适用于有重复元素的rotated array吗？ |
|
s********g
发帖数: 126 | 19 if you can modify elements,you can realize it with time complexity O(n). set
arr[|arr[i]|] to negative, and check which two missing elements, and
finally set arr back to non-negative. Be careful with array index boundary. |
|
|
c********p
发帖数: 1969 | 21 哦哦，python里的array只能塞primitive的？int, string, float什么的？。。。哎呀
呀，连python有啥data type都不知道。。。python里我都没看到string的字样。。。
感觉像说英文一样。。。is not神马的。。。 |
|
c********p
发帖数: 1969 | 22 python中array里能放啥类型？list啥都可以。
另外求一些python的小project写写 |
|
|
p****9
发帖数: 232 | 24 n(n >5)年没用java了。。。或者当年就糊涂着呢。。。那个题必须得把char array转
成string才过的了。。 |
|
z*****g
发帖数: 2 | 25 char array的hash code是内存地址。。。 |
|
h****g
发帖数: 308 | 26 我觉得是因为想用 Arrays.sort() 这个function. 然后用sort后的结果做key |
|
W***o
发帖数: 6519 | 27 终于work了，但是我的方法可能比较慢，array access 是不是太多了，有更高效的吗
？不能用太高级的API，因为作业规定：
int[] test = new int[] {1, 2, 3, 3, 3, 3, 5, 6, 8, 8, 8, 8, 8, 9, 9, 9, 9};
int i = 0;
int j = test.length - 1;
int[] copySegment;
while (i < test.length)
{
while (j > i)
{
if (test[j] == test[i])
{
for (int k = i; k <= j; k++)
System.out.print(test[k] + " ");
Syst... 阅读全帖 |
|
p*****3
发帖数: 488 | 28
以index为标准做的二分，two sorted array 找第k大的。
（另外为了避免被版上大牛喷我发誓这个是N久以前的code,俺现在不做题一心一意学
java） |
|
m**********e
发帖数: 22 | 29 Does not work. If you have even number of total elements and the median
number is between the 2 elements in one array, the result is wrong. Check
the leetcode. |
|
|
h**o
发帖数: 548 | 31 以及Find Median Of Two Sorted Arrays。 复杂度是logM+logN还是logK?我觉得是
logM+logN，为什么有人说logK?
这道题一直不想看。但据说是高频。终于在2013末看懂了。 |
|
l********r
发帖数: 140 | 32 Given an array (assume numbers, no duplicate),
print all its combinations.
My code clearly generates duplicates. :-(
public static void combination(ArrayList data)
{
combination(data, 0);
}
private static void combination(ArrayList data, int index)
{
if (index >= data.size())
return;
printArrayUpToIndex(data, index);
for (int i=index; i
{
swap(data, index, i);
combi... 阅读全帖 |
|
|
u***l
发帖数: 51 | 34 最优解时间复杂度是 O(n) 吗？
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
可能有重复值 |
|
b******g
发帖数: 3616 | 35 最优解在最差情况下的时间复杂度是O(n)，对重复的数字不多的情况，则复杂度仍为O(
log n)
这题应该是不存在最差情况都能O(log n)的解的。举个例子，假设array的所有值是1，
一共n个1。要查找2，只有遍历所有元素才能判断2不在队列中。 |
|
W***o
发帖数: 6519 | 36 今天被问到一个javascript的问题
限制是不能用任何loop，不能用任何library（只能用pure javascript），怎么来去除
一个integer array里面所有的偶数？
我的想法是：既然不让明着用loop, 我就想到了用.filter() 这个method，
比如：
var numbers = [1, 2, 3, 4, 5, 6, 7];
var oddNumbers = numbers.filter(function(val) {
return val % 2 != 0;
});
console.log(oddNumbers);
大家有什么好办法吗？ |
|
i*****h
发帖数: 1534 | 37 LC只刷了60题，今天面试碰到个题（不知道lc里有没有，粗略扫了一遍题目名字没看到
），求思路。
题目：一个array里有一组或以上重复的数字（可能只有一组，可能有几组），需要
remove第一次出现的重复的数字，然后顺序要保持和原来一样。
比如：
｛1，5，2，3，5，4，5，6｝－> {1，2，3，5，4，5，6｝
｛1，5，2，3，2，5，4，5，6｝ －>{1，3，2，5，4，5，6｝
求思路求解，谢谢了！
我能想到的就只有用hashmap. |
|
B********4
发帖数: 7156 | 38 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？ |
|
n*********u
发帖数: 1030 | 39
prev和next的两个node里的pointer改一下就行了。
array的好处是省内存。 |
|
h*******9
发帖数: 46 | 40 我们通常说的删除只是delete 这个节点的操作 并不包括找到这个点。 对于list 只需
要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面的
所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o(n
) |
|
B********4
发帖数: 7156 | 41
需要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面
的所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o
(n).
这么解释就说的通。我的新问题是为啥并不包括找到这个点? 在Java里
LinkedList.remove(int index)
要实现这个方法需要两步，第一步找到这个节点，第二步修改前后节点的指针。 |
|
c*******7
发帖数: 438 | 42 什么叫两个array的intersection啊？能不能解释一下题目。。。 |
|
y*****e
发帖数: 712 | 43 interface是这个 Iterable mergeKSortedIterators(Iterators[] iters)
也就是给每个array的iterator,然后merge.
我开始想的是用merge k sorted list的办法，用一个heap保存所有的iterator,看哪个
iterator的头个element最小,push to result，然后Move to next element。
需要一个iterator的comparator来sort iterators, 是我的comparator写的不对？还
是heap的operation错了？
不知有人做过这题吗，希望给点建议。。。。
public static class iteratorComp implements Comparator>{
public int compare(Iterator a, Iterator b){
int a1 = 0;
in... 阅读全帖 |
|
c*******e
发帖数: 621 | 44 我感觉还不如把两个array都排序了，然后各一个指针，每次移动其中较小的指针，找
到intersection
intersection 找到后，union 自然就有了 |
|
n*********u
发帖数: 1030 | 45 好像就是1D array rotate加个转圈就行了吧？转圈那个确实有点麻烦。
一共有n/2个圈要转。
试着把每个圈都铺平了，当linked list一样做rotate，也就是写个新的self.next()
function。
大概这样？
for offset in range(0, n/2):
# do while loop in python
x = offset
y = offset
while True:
# rotate x, y, by k steps
# 记不得怎么写rotate list的懒人路过
(x, y) = get_next(n, x, y, offset)
if x == y:
#回到出发点结束
break
# rotation 的 self.next() function。
# offset can be calculated with n, x, y, but it'll be available anyways.... 阅读全帖 |
|
b*******w
发帖数: 56 | 46 def rotate_by_k(matrix, k):
i = 0
while i < len(matrix)>>1:
# construct 1-d array
nums = []
x, y = i, i
while x < len(matrix) - i - 1:
nums.append(matrix[y][x])
x += 1
while y < len(matrix) - i - 1:
nums.append(matrix[y][x])
y += 1
while x > i:
nums.append(matrix[y][x])
x -= 1
while y > i:
nums.append(matrix[y][x])
y -= 1
... 阅读全帖 |
|
c******n
发帖数: 4965 | 47 heap 或者更简单， 就keep
一个100长的array sorted, 把每一个新的数插入， 再把最小的去掉
一个100 |
|
p*******0
发帖数: 5 | 48 好想法，O（array size) time. 赞一个 |
|
b*********d
发帖数: 139 | 49 Still need more people to review this paper:
paper name: Power Scaling of Chemiresistive Sensor Array Data for Odor
Classification
It is a journal of pattern recognition.
Thanks! |
|
c**i
发帖数: 6973 | 50 John Tkacik, Pricing Taiwan’s missile defense. Taipei Times, Dec. 6, 2008. http://www.taipeitimes.com/News/editorials/archives/2008/12/06/2003430467
Quote:
"I have long pointed out that Taiwan’s unique geographic location (and its
high mountains) offers great potential for US-Taiwan missile defense
cooperation. An integral part of Taiwan’s PAC-3 missile defense system is
the large phased-array missile defense radar (sometimes called “PAVE PAWS”
) that Taiwan purchased last year (now under constr |
|
