m****i
发帖数: 650 | 1 check cycle的方法，不对吧
如果
array 1 2 3 3 4
index 1 2 3 4 5
第一个就infinite loop了 |
|
q*****9
发帖数: 7 | 2
between
Is the array sorted? |
|
a*******6
发帖数: 520 | 3 Suppose the array is A[1]... A[n], and each A[i] \in {1, ..., n-1}
Corrected method:
1. Start from A[n] instead of A[1]
2. Once I1 == I2, use another O(N) time to find the length of the cycle
3. Then start from A[n] again: set I1 = n and I2 = A[A[A[A[I1]]]] (if the
cycle's length is 4); repeat I1 = A[I1] and I2 = A[I2] until I1 == I2
the
the
This |
|
a***r
发帖数: 93 | 4
yes, it is a bug, fixed, thanks for pointing it out, should have used calloc in the first place.
The algorithm should work:
If sum(from i to j)==0, then sum(0....i-1) should equal to sum(0...j)
setup an array B, such that B[i]=A[0]+...+A[i]
if A[i]+...+A[j]==0 then B[i-1]==B[j];
so only needs to find if there are duplicate items in B.
binary sort B, find duplicates, if exists then return true;
otherwise return false;
welcome to find more bugs. |
|
f****4
发帖数: 1359 | 5 原帖：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 | 6 原帖：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***t
发帖数: 276 | 7 Given an array A[], find (i, j) such that A[i] < A[j] and (j - i) is maximum.
a = 1 3 2 4 的答案是无解:) |
|
e****r
发帖数: 28 | 8 Basically Agree with nooneknow - it's not clear that what would be the expected or average big-O of darksteel solution. at least, in the case of a non-increasing sorted array, it takes much more time than O(n).
Also agree with Kirit(jack) - in the situation of interview, it's better to try the straightforward solution, get the code done, and try to reduce bugs. the coder can mention the potential sorting + O(N) post-process solution to the interviewer, though :).
btw, how many minutes do you guy... 阅读全帖 |
|
l*****a
发帖数: 14598 | 9 if the input data has fixed scope, u can use array instead of hashmap
hash_map is a C++ template which contains key/value pairs
hashtable is the internal implementation of hash_map |
|
r**********1
发帖数: 292 | 10 那array是hashtable的内部实现方式？ |
|
r**********1
发帖数: 292 | 11 “那另外一个例子，如果要计算一本书里每个字的出现次数，那简单的 array 做不到了
。因为 key 是 word，不能直接以 index 来 hash，那就用比较general的hashtable来
做。”
我是想弄清出啊。对于这个例子，用hashtable是不是如下做法？
对于每个word，我算一个hash value, 比如把每个character的ascii码加在一块得到一
个sum值，我可以把这个sum值作为hash value。
然后，我建立一个大小为1000的数组，A，初始化为0。
然后，对于每个word，算出hash value，然后以它来作为index，把相应的A[hash]进行
++操作。
对于hash value 大于1000的，进行动态扩展数组，然后继续。
这么说来，hash table 似乎是高级的动态数组。
ihasleetcode，您觉得我的理解对吗？ |
|
l******e
发帖数: 149 | 12 you don't need to physically 把所有的array拼到一起再做quick selection, but
logically.
O(kn) |
|
d**0
发帖数: 124 | 13 这k个arrays是unsorted的啊 你的做法是认为他sorted吧
in
in
log( |
|
w****o
发帖数: 2260 | 14 array里的元素是可以重复的对吧？
set里的元素是不能重复的对吧？
求intersection, union应该分别用什么数据结构和算法？
谢谢！ |
|
y*****n
发帖数: 243 | 15 hash table.
Or you can sort it and use the same strategy as merge in merge sort.
if there is k array, use the same strategy in k way merge, use an heap to
hold head elements. |
|
l*********8
发帖数: 4642 | 16 this doesn't work when N=4, k=2.
Try it. I think you'll get original array as your result. |
|
l*********8
发帖数: 4642 | 17 不需要取模的。
c++ stl 源代码里面就是用的juggling算法做array rotating. |
|
f*******n
发帖数: 12623 | 18 的确是nlogk。O(1)可以拿到top element，但是要remove它，还是要O(log k)。
假如k=n，那按照他说的就可以用这个方法O(n)去sort一个unsorted的array了。 |
|
w****x
发帖数: 2483 | 19 nlogk, 怎么会是O(n),
不过现实当中我觉得merge k array用堆不一定比不用直接比较的O(n*k)快, 甚至更慢 |
|
c**********e
发帖数: 2007 | 20 Is the answer sizeof(arr)/sizeof(int) if an integer array? |
|
c**********e
发帖数: 2007 | 21 It seems there is no way to find the size of array on heap. |
|
c**********e
发帖数: 2007 | 22 For array on stack, it works.
int arr[100];
cout << sizeof(arr)/sizeof(int) << endl;
You do get 100. Though I am not sure if it is system dependent. |
|
w****o
发帖数: 2260 | 23 在这个班上看见过，但是具体的题的描述我不记得了。
好像是给一个 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?
到底面试的时候，问到的是哪种情况？
谢谢！ |
|
w****x
发帖数: 2483 | 24 //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 ... 阅读全帖 |
|
x******g
发帖数: 319 | 25 given an array, find all possible sets of elements which sums as 0.
for example:
input:
[-1, -2,-3, 3, 4, 5]
output:
[-1, -2, 3]
[-2,-3,5]
[-3, 3]
有什么好办法呀？ |
|
p******9
发帖数: 47 | 26 将array分为正负两组，如果每组的和有限的话，可以做DP，时间复杂度SUM*N，然后
回溯输出所有解 |
|
q***y
发帖数: 236 | 27 LeetCode Jump Game II. 从右向左，搞个array S[]记录每一位的最少步数。当前最少
等于min{S[i+1],...S[i+A[i]]}+1。最坏情况O(n^2)。虽然过了online judge。
求更好解法。 |
|
j*****n
发帖数: 1545 | 28 那如果这个array 不是 positive number, 是non-negative呢， 有可能会有0，能用同
同样的思路吗， 昨晚面试被问的就是non-negative的情况，想了半天也没想出来. |
|
W***u
发帖数: 81 | 29 原题是,Write a method to sort an array of strings so that all the anagrams
are next to each other.
看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
入进去的，真心不知道这样的查找怎么能够保证O(1).
求各位前辈高人解疑释惑。 拜谢！ |
|
t*****e
发帖数: 53 | 30 Can we design an algorithm that can find the triplet in an unsorted array (
including both positive and negative numbers) that sum up to a defined
number? Requirement: the runtime should be o(nlogn).
I can think about alot of O(n^2) way. Do you think this problem has a
solution with O(nlogn).
thanks in advance. |
|
a*******y
发帖数: 1040 | 31 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 | 32 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). |
|
l****c
发帖数: 782 | 33
you lost one more step in each function. Think about "ABBC". Your approach
will find 0 as the left edge.
Try to add this before return in:
if (array[low]
else return low; |
|
c****g
发帖数: 85 | 34 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 | 35 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 | 36 贴个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[... 阅读全帖 |
|
c****g
发帖数: 85 | 37 哈哈，good one.
你用了空阵列来对付exceptioanl cases，这样程序简单多了。
Java里没有空阵列，所以我用了很多if语句。但是在你python版的启发后，我可以定义
left,right indexes for assumed empty arrays。
Thanks! |
|
w****x
发帖数: 2483 | 38 一种方法是看所有的n subset.
一种方法是先随便分成两个n的sub array, 然后再while循环里试图交换两个element以
使得| sum A1 - sum A2 | 小余当前最优解, 终止条件是找不到这样的swap |
|
t******t
发帖数: 21 | 39 how about greedy?
sort the array say {1,2,3, 80, 85, 99, 100, 1000}
pick 1000 first in A1
pick 100 in A2
if (sum1 -sum2)900 > next max 99
pick next min 1 in A1 and next max 99 in A2
else if sum1 > sum2 pick next max in A2, then repeat recursively |
|
l*****a
发帖数: 14598 | 40 ArrayList for the first 3 requirements
for the 4th, create a new array as 2,10,10,10,80 and then u can get it
element |
|
g**e
发帖数: 6127 | 41 array list append不是每次都是O(1)吧 |
|
|
l****c
发帖数: 782 | 43 从后往前merge就不需要其他space了，困困。
array. |
|
m******6
发帖数: 82 | 44 把B里边值插入A种的合适位置，然后A种的元素进行移动
array. |
|
c********t
发帖数: 5706 | 45 use K min-heap, O(N*log(k))
如果用 quicksort方法，找N/2th 比较复杂，
1 取A1,A2..median元素 A1[N1/2], A2[N2/2]... 存入一个一维数组middle[K];
2 找到middle里的min Ai[Ni/2],
3. change Ai start index = Ni/2+1, 找到新的Ai median,置换掉middle[i];
4. 问题变为找剩下的第N/2 - Ni/2的元素
5. 循环2-4，直到第四步找剩下1个元素，既是middel[k]的min
应该是O(K (logN)^2)
但感觉如果把数组换成一个min-heap存 struct 会得到 O(logK （logN
)^2);
array
the |
|
c********t
发帖数: 5706 | 46 quicksort? 与求kth in two sorted array 一样吧？ |
|
f*****e
发帖数: 2992 | 47 用短array的median去分离长的，然后recurse。 |
|
f*****e
发帖数: 2992 | 48 然后就继续recurse，新的arrays长短就不一定了。 |
|
c********t
发帖数: 5706 | 49 quicksort? 与求kth in two sorted array 一样吧？ |
|
f*****e
发帖数: 2992 | 50 用短array的median去分离长的，然后recurse。 |
|
