h******o
发帖数: 334 | 1 怎样才能不覆盖前面存？我想每一列存后，就search 一个数据。完整的code如下：
Write a binary search method, which gets a 2D array and a query as arguments
and returns the number of times that the query occurs in the array. The 2D
array is sorted by columns but not by row.
public static int count(int[][] array, int query) {
int searchTotal = 0;
//iterate each 2D array' column
for (int c=0; c < array[0].length; c++){
searchTotal += biSearch(array, query, c);
}
return searchTotal;
}
private sta... 阅读全帖 |
|
m********g
发帖数: 272 | 2 O(n) 的解法：
array = {1, 2, 4, 5, 6, 7, 9, 12}, k = 3，length = 8
1. 先reverse 前面 5个数 {1，2， 4，5，6} －－>｛6, 5,4,2,1｝(length - k)/2
2. 再reverse 后面3个数｛7，9，12｝－－> {12, 9, 7} k/2
现在的array ＝ ｛6， 5， 4，2，1， 12， 9，7｝
3. 现在把整个array reverse ＝ ｛7 9 12 1 2 4 5 6 ｝length/2
所以total runtime ＝ （length -k ）/2 + k/2 + length/2 = length
code:
==========
private static void rotate(int[] array, int k)
{
int length = array.length;
k = (k % length + length) % length;
for(int ... 阅读全帖 |
|
x***y
发帖数: 633 | 3 Actually, we can do some extension. For m arrays, we can convert to m-1
arrays problem with the time complexity being timed O(logn). Then, convert
into m-2 arrays, m-3 arrays, and in the end 2 arrays, which is O(logn), 1 array
which is O(1), we can conclude that the time efficiency is O((logn)^(m-1)) for m arrays with same length m.
Also, this can be extended into arrays with different lengths as two arrays with different lengths..... |
|
h******o
发帖数: 334 | 4 Java 有一个2D array: int[][] array; 我想把这个2D array的每个column导入到一个
新的1D array, 下面的方法不知道问题在哪里？ 多谢！
int[] column = new int[array.length];
for (int c = 0; c < array[0].length; c++) {
for (int i = 0; i < array.length; i++) {
column[i] = array[i][c];
}
} |
|
p**z
发帖数: 65 | 5 用 logic array 来 index 另一个 array：这两个 array 都必须是 numpy array。如
果用了 list，就会出错。例子：
>>> a = [1,2,3,4,5]
>>> b = [True, True, False, False, False]
>>> a[b]
Traceback (most recent call last):
File "", line 1, in
TypeError: list indices must be integers, not list
>>> a = np.array(a)
>>> a[b]
array([2, 2, 1, 1, 1])
>>> b = array(b)
>>> a[b]
array([1, 2]) |
|
f****4
发帖数: 1359 | 6 找到一个对的O(N)的解法
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
This is a pretty good puzzle. You can actually find the cutoff and a
description of exactly which pairs are in the solution in less than O(N)
time, but outputting all the solutions takes O(N) time, so it doesn't help
you overall. This won't be much of a hint, but finding the cutoff point can
be done in O(sqrt(N)*log2N) time. Forgive me for not writing code, but this
gets pretty nitty-gritty in spots.
I think of the pro... 阅读全帖 |
|
f****4
发帖数: 1359 | 7 找到一个对的O(N)的解法
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
This is a pretty good puzzle. You can actually find the cutoff and a
description of exactly which pairs are in the solution in less than O(N)
time, but outputting all the solutions takes O(N) time, so it doesn't help
you overall. This won't be much of a hint, but finding the cutoff point can
be done in O(sqrt(N)*log2N) time. Forgive me for not writing code, but this
gets pretty nitty-gritty in spots.
I think of the pro... 阅读全帖 |
|
t****t
发帖数: 6806 | 8 The array size information is bound to the array type. But if the function
you called does not know the type of the array, i.e. doesn't know the lenght
of the array, then you can not know the length of array. :)
That is to say, you have to know the length of array before you know the
length of array. So the answer is no for C language. For C++, this can be
solved with template.
Please read C FAQ, there's a section for array and pointer.
type. |
|
|
c***2
发帖数: 838 | 9 Performance of done's solution: (for array size of 10)
======================================================
Input Array:
-45 -85 -1 -37 -21 -11 -5 52 -57 46
comparisons=33
longest_inc_sub:
length=5
startIdx=3
Sub-array:
-37 -21 -11 -5 52
Input Array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
comparisons=12
longest_inc_sub:
length=10
startIdx=0
Sub-array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
Input Array:
52 46 -1 -5 -11 -21 -37 -45 -57 -85
comparisons=9
longest_... 阅读全帖 |
|
g**u
发帖数: 504 | 10 看我的这个行不行？
#include
#include
using namespace std;
int maxShiftedSortArray(vector& array){
int n=array.size();
if(n==1)
return array[0];
int l=0;
int r=n-1;
int m;
while(l
m=(r+l)/2;
if(array[m]>=array[l]){
l=m;
}else{
r=m-1;
}
}
return max(array[l],array[r]);
} |
|
f*******n
发帖数: 12623 | 11 为什么sort会需要创造一个新的array？你调用的另外的这个sort用这个array干嘛？给
它一个Object[]不行吗？
Java的array在运行时知道自己的元素类型，所以不同类型的array在运行时是不同的。
但是好像T这些类型参数在运行时不存在。
反正你调用的另外的这个sort也不会知道你给它的东西是不是T[]，你可以创造一个
Object[]给它，假装是T[]：
Object[] tmp = new Object[a.length];
sort(a,(T[])tmp, 0, a.length-1);
但是最好是另外的这个sort根本就接受Object[]；反正对它不会有区别。
如果你真的想创造正确类型的array，你可以从你运行时已经有的T[]那里得出元素类型
，跟着用那个来创造新的array。这样不需要分开再传递一个类型。
Class clazz = (Class)a.getClass().getComponentType();
T[] tmp = Array.newInstance(clazz, a.length);
sort(a,tmp, 0, a.le... 阅读全帖 |
|
c***2
发帖数: 838 | 12 Using brute-force
========================
Input Array:
-45 -85 -1 -37 -21 -11 -5 52 -57 46
comparisons=21
longest_inc_sub_bf:
length=5
startIdx=3
Sub-array:
-37 -21 -11 -5 52
Input Array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
comparisons=10
longest_inc_sub_bf:
length=10
startIdx=0
Sub-array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
Input Array:
52 46 -1 -5 -11 -21 -37 -45 -57 -85
comparisons=10
longest_inc_sub_bf:
length=1
startIdx=0
Sub-array:
52 |
|
c***2
发帖数: 838 | 13 /* longest contiguous increasing sub-array : improvement */
int longest_inc_sub(int array[], int size, int *start)
{
int max,len,i;
int from,to,max_from;
int comparisons=0;
max=len=1;
max_from=from=to=0;
i=0;
while(1){
/* advance to next block */
to = from+len;
if(to>=size) break;
/* looking backward */
i=to;
while((i>from)&&(array[i]>=array[i-1])){
i--;
len++;
comp... 阅读全帖 |
|
e********r
发帖数: 2352 | 14 bool array [] = {T, T, T, T, T, T, T, T, T, …}
unsorted int array
int array2 [] = {3, 1, 2, 0, -1, …}
for(int i = 0; i < array2.size(); i++)
{
if(array2[i] > 0)
array[array2[i]] = false;
}
for(int i = 0; i < array.size(); i++)
if(array[i])
return i;
刚想的答案，看一下符合你的要求吗. |
|
d****p
发帖数: 685 | 15 Yes, I agree with you that sizeof(array)/sizeof(array_elem) is better.
Lz's code however technically is right - declare a function which takes in a
pointer to an array whose length is known at compile time and returns a
pointer to an array whose length is also known.
A pointer to an array is slightly different with an array from the
perspective of compiler though the sizeof operator will produce the same
result for them.
Basically you cannot return an array from a function but you can return a
p |
|
c**t
发帖数: 2744 | 16 var qry = from b in Array2
select Array.IndexOf(Array1, b);
say
Array 1 = {1, 3, 2, 4}, idx is 0, 1 ,2 3
Array 2 = {1, 2, 3, 4}
how do i know it's idx is actually 0, 2, 1, 3 from Array 1 ?
is there such function ? |
|
d********w
发帖数: 363 | 17 Given an array containing integers, you are required to find the indexes of
the smallest sub-array which on sorting will make the whole array sorted.
For e.g. 1 2 3 4 6 5 7 8 9 10
Output 4 5
Consider that such an array is somewhere in middle of the array. |
|
g**f
发帖数: 414 | 18 刚写了一下，应该work。
O(1) space, O(n) time.
bool SumToS(int* array, const int len, const int S,
unsigned& ndx1, unsigned& ndx2)
{
int i = 0, j = len-1;
while (i != j) {
if (array[i] + array[j] < S) ++i;
else if (array[i] + array[j] > S) --j;
else {ndx1 = i; ndx2 = j; return true;}
}
return false;
} |
|
i**********e
发帖数: 1145 | 19 HashMap 是 one to many relationship，hashtable one to one.
看情况，主要 hashtable 和 array 的区别在于前者比较 general：
比如，要计算一个字符串里每个字母的出现次数，用简单的 array 再也适合不过了。
如果只是 ascii 字符，那 256 的大小就够了。
那另外一个例子，如果要计算一本书里每个字的出现次数，那简单的 array 做不到了
。因为 key 是 word，不能直接以 index 来 hash，那就用比较general的hashtable来
做。
还有另一种情况 hashtable 是比 array 好的，就是节省空间。为什么呢？
比方你的 key 的range在于 1 - 1,000,000，但是最多你只会 insert 不超过 100 个
element。那用array来做，那相当于只用数组里的100个，其余的都是空的，非常浪费
空间。但是 hashtable就没有这个问题，因为是 dynamic 的数据结构。 |
|
p*****i
发帖数: 197 | 20 问一道题目，how to find the majority element in an array?
例如 一个array里有 4,2,3,1,2,2,2 就要return 2(因为2出现的次数是4, 4超过了
array 长度的一半）。相反，如果array 里是4,2,3,1,2,2,3 就要return -1（因为没
有数超过array 长度的一半）。
如何在 O(n) 的time complexity 和O(1) 的space里完成？ |
|
S*****e
发帖数: 229 | 21 我觉得可以用bit vector，size就是array size，扫一遍array，如果array中的整数在
bit vector之内，相应的bit变成1，之后再扫一遍bit vector，第一个0表示最小的不
在此array的数。 |
|
b*******e
发帖数: 217 | 22 incorrect.
see example 3214
first round (1) 32 needs swap
get 1432
second round (2) 4 need to swap
get 1324
not sorted.
I guess needs to use some advanced data structure like stack....
keep tracking the local min.... then pop us the elements larger than the
local min and insert them to the end one by one.
(1) push 32 into stack.
(2) when hit 1, see 1 is local min
(3) pop up 2,3 and insert them to the back of the array
(4) now array is 1423.
(5) the array pointer now go to 1 (note we can track th... 阅读全帖 |
|
f**********n
发帖数: 258 | 23 The problem is "Minimum number of moves to make an integer array balance".
Move is defined as reducing one element in array and increase anther integer
.
Balance is defined as the maximum difference between two integers in whole
array is 1.
lo=floor(average of array x)
up=ceil(average of array x)
lo_sum =the sum of all (lo - x[i]) for each x[i]
up_sum=the sum of all (x[i]-up) for each x[i]>up
My solution is max(lo_sum, up_sum)
Here are several examples with my solution going through.
[1 2 3]... 阅读全帖 |
|
f*******w
发帖数: 407 | 24 我是刚接触actionscript没到一个星期的新手，请版上的高手指教：
I use following flash actionscript code, got from online, to load the "
Loading.txt" file:
var myTextLoader:URLLoader = new URLLoader();
myTextLoader.addEventListener(Event.COMPLETE, onLoaded);
function onLoaded(e:Event):void {
var myArrayOfLines:Array = e.target.data.split(/\n/,",");
}
myTextLoader.load(new URLRequest("Loading.txt"));
In "Loading.txt", the data of object in a row is (Dim1 Dim2 Dim3 OX OY OZ)
is:
60,12,9,-50,-50,50
84,12,9, 50, 50,50
Then... 阅读全帖 |
|
g*****g
发帖数: 34805 | 25 People usually do a for loop to check,
boolean found = false;
for(i=0; i
if(o.equals(array[i]) {
found = true;
break;
}
}
if you are really lazy, try Arrays.asList(array).contains()
For trivial array, shouldn't be much different in performance. |
|
z**********r
发帖数: 86 | 26 我现在在学习Java，以前会C/C++，但是主要是用C和Matlab。
我用的是Weiss "Data Structures and Problem Solving Using Java 3rd Edition"，
现在看到了第四章，关于继承。
里面有一道习题（4.23）：
Write generic method max2, which accepts an array and return an array of
length two representing the two largest item in the array. The input array
should be unchanged. Then use this method on String type.
最下面是我的代码。现在我的问题是，我知道创建一个generic array是不被允许的。
StackOverflow上面有人给了一种方法：
AnyType []result=(AnyType []) new Object[2];
这种方法编译没有错的，但是运行的时候会出现[Ljava.lang.Object; ... 阅读全帖 |
|
f*******n
发帖数: 12623 | 27 You can't. T doesn't exist at runtime. It's an illusion. Just remove T and
ask yourself how to do it. If you cannot do it without T, then you cannot do
it with T either:
public class SpecialArray {
Object[] createSpecialArray()
{
return (Object[])Array.newInstance(???, 10);
// How to get T?
// You do not pass anything into this method
}
}
Your problem is that arrays in Java know their component type at runtime. If
you do new String[5], the object knows it's an... 阅读全帖 |
|
s*****w
发帖数: 1527 | 28 say
Array 1 = {1, 3, 2, 4}, idx is 0, 1 ,2 3
Array 2 = {1, 2, 3, 4}
how do i know it's idx is actually 0, 2, 1, 3 from Array 1 ?
is there such function ? |
|
x***y
发帖数: 633 | 29 A[n/2]=6, B[n/2]=33, C[n/2]=100, So A':6 10 18 C': 7 9
To find the median M' of A' C', O(log(max(|A'|, |C'|)))=O(logn).
if M' < B[n/2], B is left with B[22 28 33], and find data in A'less than M'
, find data in C' less than M', O(logn), and eleminate them.....
All problems of this kind is essentially 2 array problem, and the time
efficiency is O(logn) * time for finding the median and delete operation in each array. For sorted array, 2nd term is O(1), but for an partially sorted array A'+C',th |
|
y*********e
发帖数: 518 | 30 贴一贴我的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.
|
|
c***2
发帖数: 838 | 31 /* longest contiguous increasing sub-array : brute-force */
int longest_inc_sub_bf(int array[], int size, int *start)
{
int max,len,i;
int from,max_from;
int comparisons=0;
max=len=1;
max_from=from=0;
i=0;
while(1){
i=from;
while((i=array[i])){
i++;
len++;
comparisons++;
}
comparisons++;
if(len>max) {
max_from=from;
max=len;
... 阅读全帖 |
|
J*****u
发帖数: 30 | 32 给定一个array,问minimum sub-array的和与sum value相等.array里可能有正数,负数
和0,sum value也有可能是正负和
0.谢谢! |
|
s**x
发帖数: 405 | 33 This is exactly equivalent to finding loop in a singly linked list.
The singly linked list is defined with entry A[0] of the input array as the
HEAD node, and the numeric value of each array element as the array index
for the NEXT node. Since every array element A[i] is between 1..(n-1), all
the nodes have valid NEXT node pointers. Thus by sequentially traversing the
list you will encounter a loop.
Just use two iterators I1 and I2, initialized to A[0] and A[A[0]]. Then
while (I1 != I2), let I1 =... 阅读全帖 |
|
c*******r
发帖数: 309 | 34 Given an array of random numbers. Find the longest consecutive sequence.
For ex
Array 100 3 200 1 2 4
Ans 1 2 3 4
Array 101 2 3 104 5 103 9 102
Ans 101 102 103 104
Can we do it in one go on array using extra space??
我想到的方式是先sort， 然后用index来存,然后记录max长度. 不断更新新的index指
针.
不过据说复杂度要控制在o(n).
没什么好的想法啊 |
|
c**j
发帖数: 103 | 35 ding! Can we do it without sorting??
请问Bayesian1， 还有link没？
加个条件： 这个题如果还要要求 答案是*连续位置的*的subarray呢？
e.g.:
input: 4,5,1,5,7,4,3,6,3,1,9
sort以后1，1，3，3，4，4，5，5，6，7，9
output{5,7,4,3,6}
check careercup:
http://www.careercup.com/question?id=11256218
Microsoft Interview Question about Algorithm asm on October 19, 2011
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
39
http:/... 阅读全帖 |
|
f*******n
发帖数: 12623 | 36 可以 O(k*log(n)^2)
Binary search in the first array for the index closest to the median. At
each step, binary search in the other (k-1) arrays for the current value in
the first array. Then add the indexes to see if we are before or after the
median. At the end, we are down to one element and we also know the index in
the other arrays. The answer is in one of these.
The bigger binary search is log(n), at each step, we need to do (k-1) * log(
n), so multiplied together we get O(k*log(n)^2) |
|
C***U
发帖数: 2406 | 37 #include
#include
#include
#define MAX 10000
int main(int argc, char *argv[]){
std::vector numbers1;
std::vector numbers2;
int k = atoi(argv[3]);
if(argc < 4)
std::cout << "we need 2 files and a number." << std::endl;
std::cout << "we need find " << k << "th number" << std::endl;
std::cout << "reading first array of numbers ..." << std::endl;
std::ifstream f1(argv[1]);
if(!f1){
std::cout << "cannot open... 阅读全帖 |
|
f*****e
发帖数: 2992 | 38 给定两个arrays，有一个长，有一个短，然后
就是找短array的median在长array中的位置啊，耗时O(lg(size of long array))。
然后继续recurse。 |
|
f*****e
发帖数: 2992 | 39 给定两个arrays，有一个长，有一个短，然后
就是找短array的median在长array中的位置啊，耗时O(lg(size of long array))。
然后继续recurse。 |
|
z****p
发帖数: 18 | 40 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 | 41 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 | 42 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? |
|
h***t
发帖数: 43 | 43 电面，碰到传说中的“国人大哥”，上来考了rotate array (leetcode 原题)，很快搞
定。接着说要出一个2D array rotation问题，当时还庆幸又是原题（rotate image）
，大哥不错啊，知道放水。
接着听就不对劲了。不是90度旋转，而是要把每一个element都顺时针移动 k steps。
比如n = 5, k = 3,
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
变为
16 11 6 1 2
21 18 17 12 3
22 19 13 7 4
23 14 9 8 5
24 25 20 15 10
本来想这两道题一起出，我就用一下rotate array的程序吧，就是把每一个circle的
element取出来放到一个Array里，rotate完了，再放回去，但大哥说复杂度太高。再想
，，，
那就只有用rotate image的思路了，一个个挪，时间O(n*n),空间O(1)。
思路对了，接着写程序，才发现没那么简单，而且时间也快到了。... 阅读全帖 |
|
f******n
发帖数: 198 | 44 - Array.IndexOf() for finding one element.
- Array.Find() and its variations for general purpose search.
- Array.BinarySearch() if the array is pre-sorted.
All of these are static, so they're not very discoverable... |
|
f******r
发帖数: 2975 | 45 Here I have one array index(1xN), the element of index is integer between 1
and k
and another array A(k,N)
Now I wanna create a new array
so that
B(i,j) = A(index(i),j)
My array is very very big
Any quick matlab code for that?
Thanks a lot! |
|
c**********e
发帖数: 2007 | 46 【 以下文字转载自 Statistics 讨论区 】
发信人: qqzj (小车车), 信区: Statistics
标 题: Python:请问如何把list变成structured array。 (转载)
发信站: BBS 未名空间站 (Fri May 1 15:53:30 2009)
发信人: qqzj (小车车), 信区: Programming
标 题: Python:请问如何把list变成structured array。
发信站: BBS 未名空间站 (Fri May 1 15:52:21 2009)
我总是把数据从.csv或者SQL里面读入，成为list。但是现在要把他们变成容易操作的
形式。用了Numpy以后，array(whatever）把所有的东西都变成了一种形式。很不方便
。请问用没有办法直接把数据从list形式转化成structured array？多谢指教。 |
|
c*******d
发帖数: 353 | 47 I would like to hear your comments on my design of this array class. The
purpose is to provide a fast, easy to use multi-dimensional array container.
/*
* A C/C++ OO approach to use multi-dimenisional array in HPC environment.
*
* Goal: speed, ease of use, robustness
*
* Design advantage:
* By using 1D array as data container, CPU prefetching, caching, TLB
* features are used to make data access faster. By providing error checking
* in access methods, bounds check can be easily done. Access me |
|
h*****g
发帖数: 944 | 48 【 以下文字转载自 JobHunting 讨论区 】
发信人: huasing (Menlo Park), 信区: JobHunting
标 题: C++里get array size的问题
发信站: BBS 未名空间站 (Wed Jul 21 13:45:52 2010, 美东)
C++里是不是现在没有现成的get array size/length的function??
如果没有的话，我在网上看到了一个code
#include
template char (&array(T(&)[N]))[N];
#define length(a) (sizeof a / sizeof a[0])
int main()
{
int a[10];
std::cout << sizeof array(a) << '\n';
std::cout << length(a) << '\n';
}
请问这个code对所有的data type都work吗？ 我试试了，好象是可以的。中间有什么错
误吗？ |
|
B********r
发帖数: 397 | 49
would
In fun1, str is array name of "ABC". When you return an array name whose
content was destroyed after returning, you can't get a right result.
In fun2, str is a pointer which points to an array "ABC". Since "ABC" is
constant and stays in the memory and what you return is the actual address,
you can find "ABC" in main(). (*str)[] just different from *str[] as a
pointer, instead of a pointer array. |
|
k**********g
发帖数: 989 | 50 O(N) (best case O(1)) if the input values are integers and the range is
finite (and relatively small compared to the array size.)
Suppose the values in the input array are bounded, i.e. input x[k], where
MIN <= x[k] <= MAX. N is the size of input (1 <= k <= N).
Allocate an array of size (MAX - MIN + 1), that is, one element for each
possible integer value between [MIN, MAX]. Each element can contain either a
special value "UNASSIGNED", or an unsigned integer which is an index (k)
from the input ... 阅读全帖 |
|
