j**l
发帖数: 2911 | 1 是这样的，Hash表初始为空，如果新来一个元素，如果不在表内才动态插入。如果已经
在表内的就不做任何操作。
你可以参考一下STL的vector,可以为空，可以先预留一定空间，可以动态增长。当然在
内部存储空间不足时候需要重新分配并扩大可用存储空间，需要一些额外开销。
比如数组为 1 1 2 2 2 3 4 4 5, 大小为9
Hash表只需要存1, 2, 3, 4, 5，大小为5 |
|
|
B*****t
发帖数: 335 | 3 这个本质跟两个等长数组找median道理一样，没什么区别，O(log(n+n))变成了
O(log(m+n))
多
n |
|
h**6
发帖数: 4160 | 4 访问动态分配的数组a[0]在某些情况下指令会少一个字节，可能少用一个CPU周期。其余不管a[1]到a[10000]都是一样的。 |
|
j**l
发帖数: 2911 | 5 You are given an array [a1 ... an] and we have to construct another array [
b1 To bn] where bi = a1 * a2 * ... * an / ai. You are allowed to use only
constant
space and the time complexity is O(n). No divisions are allowed.
解法是引入两个辅助数组
Si = a1 * a2 * ... * ai
Ti = ai * a(i+1) * ... * an
则bi = S[i-1] * T[i+1]
但是有题目要求的O(1)空间和O(n)时间的解法么？ |
|
j**l
发帖数: 2911 | 6 假定n = 5，数组下标从1开始。
int iter = 1;
int i;
for (i = 1; i <= 5; i++)
{
b[i] = iter;
iter *= a[i];
}
iter = 1;
for (i = 5; i >= 1; i--)
{
b[i] *= iter;
iter *= a[i];
} |
|
B*****t
发帖数: 335 | 7 每个数都超过数组总数1/4， 故3个数占了3/4以上，剩下的数只占1/4一下。
剩下的做法和n个数中有一个数的个数超过总数的1/2的道理一样
来。 |
|
s******i
发帖数: 44 | 8 如果扫描数组一次，建立一个类似hashtable的结构，那所有类似问题都能解决了，是
不是还有更巧妙的方法呢？ |
|
j**l
发帖数: 2911 | 9 是Maximum SubArray Sum的变体,这里有几个要求，一个是连续，一个是最长，一个是
和小于等于一个定值T
假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
首尾两段，长度加起来最短且其和大于等于U，剩下的中间那截自然就是满足题目的最
长子数组。
有三种情况
1) 只有从首开始的一段
2) 只有以尾结束的一段
3) 首尾两段都有，且不相交
对这三种情况取最小就可以解答
由于首尾两端都是固定的，那么算出那么算出a1...ai的和，以及aj...aN的和，都只要
O(N)时间, 所以1), 2)都是O(N)时间可解的
难办的是3), 据说可以处理一下，用binary search的思想在NlogN解决。想了半天未果
，请帮忙解答，谢谢。 |
|
i*****e
发帖数: 113 | 10 批判一下我的程序
假设数组是[0..k-1], [k..n-1]，这样看起来舒服一些
第一个是递归的形式，尾递归所以空间没问题，第二个改写成了循环
考虑最差情况，k=1，这时候时间复杂度是O(n)
using namespace std;
void sort_recurse(int a[], int n, int k)
{
int ll = k, lr = n - k;
if (ll == 0 || lr == 0) {
return;
}
if (ll == lr) {
for (int i = 0; i < ll; ++i)
swap(a[i], a[k+i]);
return;
} else if (ll < lr) {
for (int i = 0; i < ll; ++i)
swap(a[i], a[n-k+i]);
return sort_recurse(a, n - ll, k);
} else { |
|
p*u
发帖数: 136 | 11 这个问题是有解的。不过面试考这样的题，太不厚道了，完全是超出能力范围的题目。
这是TAOCP上的一个练习题，有一篇196x年的论文专门给了解法的。
基本思想是把数组分成 sqrt(n + m) 这样的块，然后重复利用空间。
1，前n个数有序，后m个数有序。把前n个数和后m个数，分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
3，对于作为swap空间的最后一个块，直接做冒泡排序。时间复杂度O(n + m)，空间复杂度是O(1)的。
大致思想是上面这样的，具体细节我也记不清楚了。可以看看TAOCP，上面有习题解答。 |
|
i*****e
发帖数: 113 | 12 嗯，的确有问题
前些日子看到一道面试题，第一子题目是把一个有序数组给分段了，第二个是如何合并
，大致这个意思。所以先入为主了
删原帖 |
|
K******g
发帖数: 1870 | 13 就像binary search一样。 不知道 a[l]<=a[m]<=a[r]是不是“数组是升序排列”的充
要条件。 |
|
h**6
发帖数: 4160 | 14 当然不可以了。
两三次比较最多能发现反例证明数组未排序。要验证已排序的话必须逐个比较。 |
|
K******g
发帖数: 1870 | 15 那用二分法可以检测一个数组是否排序吗？
如果排序的，和O（n)算法一样
如果不是排序的，那么就是O(lgN）了
可以这么说吗 |
|
K******g
发帖数: 1870 | 16 如果数组不是排序的，就是O(lgN）啊，如果是排序的，那就要搜索到底，和O（n）一
样啊 |
|
l****i
发帖数: 396 | 17 这个数组里元素的值有范围么？
有的话，我觉得用bitmap。
没有的话，就不知道了。。。等解答 |
|
w*********s
发帖数: 277 | 18 我现在有一些keyword和keyword所对应在文本中“出现的次数”
如何使用二维数组来对“出现的次数”进行降序排列，输出打印结果呢？
用的是perl，需要速度比perl自带的sort()要快。perl里面的sort()是qsort。
请指点！
谢谢！
5个包子！ |
|
h***n
发帖数: 276 | 19 如果只是需要临时分配不确定大小数组的话
用gcc，可以支持以下的语法
void foo(int n) {
int m[n];
...
} |
|
h**k
发帖数: 3368 | 20 来自主题: JobHunting版 - 有A[i] 复杂度是O(mlgN)，m是数组长度，N是条件里的a(i)
于m的线性算法。 |
|
B*M
发帖数: 1340 | 21 http://en.wikipedia.org/wiki/Longest_increasing_subsequence
Efficient algorithms
The algorithm outlined below solves the longest increasing subsequence
problem efficiently, using only arrays and binary searching. It processes
the sequence elements in order, maintaining the longest increasing
subsequence found so far. Denote the sequence values as X[1], X[2], etc.
Then, after processing X[i], the algorithm will have stored values in two
arrays:
M[j] — stores the position k of the smallest val... 阅读全帖 |
|
B*M
发帖数: 1340 | 22 我run了程序，去掉P，一样可以返回数组，
不知道是不是我的test case太简单了，
我试了好几个，都没试出来，P什么时候才是必要的，
分析也看不出来，好像M就足够了， |
|
|
x******g
发帖数: 41 | 24 不是，mid分段扫描是linear的
二分是说找mid的值是二分的
所以复杂度是O(NlogM) N是数组的size，M是summation
大牛们correct me if i am wrong, thanks |
|
|
g***s
发帖数: 3811 | 26 非负整数数组 is ok for binary search..
yes if all x[i] are non-negative numbers (integer is not required)
same.
O(K*N*N)
Non-negative numbers can be handled by binary search in O(N*N).
sum(i,j) : sum of (a_i, a_i+1,..,a_j) O(n*n)
sort sum(i,j) O(nlogn)
binary search in the sorted sum(i,j) O( n log n)
Total time is O(n^2) |
|
|
c****p
发帖数: 6474 | 28 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
的相对顺序
比如：
input:
1,7,-5,9,-12,15
ans: -5,-12,1,7,9,15
要求时间复杂度O(N),空间O(1) |
|
b**********g
发帖数: 90 | 29 从后往前扫瞄到遇到第一个负数，
把这个负数与它前面的正数交换，直到，它前面也是负数
这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
比如：
3,4,1,7,-5,9,-12,15
-->
3,4,1,7,-5,-12,9,15
-->
-5，-12，1,7, 3，4，9,15
-->
-5,-12,3，4，1，7,9,15
负数序列和正数序列的交换比较tricky，但是应该是可以保证O(N)的，
以 3,4,1,7,-5,-12 为例
先把-5，-12同正数序列的头两个交换
得到
-5,-12,1,7,3,4,
然后，把，1,7,同3，4交换保证位置：
得到
-5,-12,3,4,1,7,
以此类推。
把m 连续的负数序列 同 之前的 k连续正数序列交换，可以在 m+k时间内完成， |
|
c****p
发帖数: 6474 | 30 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
的相对顺序
比如：
input:
1,7,-5,9,-12,15
ans: -5,-12,1,7,9,15
要求时间复杂度O(N),空间O(1) |
|
b**********g
发帖数: 90 | 31 从后往前扫瞄到遇到第一个负数，
把这个负数与它前面的正数交换，直到，它前面也是负数
这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
比如：
3,4,1,7,-5,9,-12,15
-->
3,4,1,7,-5,-12,9,15
-->
-5，-12，1,7, 3，4，9,15
-->
-5,-12,3，4，1，7,9,15
负数序列和正数序列的交换比较tricky，但是应该是可以保证O(N)的，
以 3,4,1,7,-5,-12 为例
先把-5，-12同正数序列的头两个交换
得到
-5,-12,1,7,3,4,
然后，把，1,7,同3，4交换保证位置：
得到
-5,-12,3,4,1,7,
以此类推。
把m 连续的负数序列 同 之前的 k连续正数序列交换，可以在 m+k时间内完成， |
|
r*******y
发帖数: 1081 | 32 第二个数组有重复也不会影响输出结果吧？
输出的不还是啊 'a'吗？ |
|
t*******i
发帖数: 4960 | 33 如果都是ｌｅｔｔｅｒ的话，c里面就那么２６个ｌｅｔｔｅｒ，固定一个ｌｅｔｔｅｒ,从a-z扫描一遍两个数组
，count一下就知道是不是重复了。复杂度是 ２６（元素总和），也是 ｏ(ｎ)吧
当然如果用个树组 ａｒｒ［２６］就可以扫一遍了。 |
|
a********1
发帖数: 750 | 34 array of string.
ｅｒ,从a-z扫描一遍两个数组 |
|
r*******g
发帖数: 1335 | 35 为什么不是先对两个数组排序，然后按照顺序比较，这样就可以linear给出duplicate
了，但是需要额外空间。 |
|
y******n
发帖数: 47 | 36 如果数组元素只是ASCII字符的话, 只有255个可能的字符, 那么hashtable不就是o(1)
space的么?
这样就行了 int a [256]; |
|
H****s
发帖数: 247 | 37 相邻数之间的差存一个数组 O(n)
然后再选择最大的k个差值 O(n)
总复杂度O(n) |
|
c********1
发帖数: 52 | 38
partition,最大是整个
我觉得我没把问题讲清楚。。。这个不是partition的问题
比如说给一个数组 [1,4,6,7] k = 2
那么我们选1和7就是最优的 因为差是6最大
如果k=3我们选1，4，7
差是3 (maximize the minimal difference) |
|
H****s
发帖数: 247 | 39 相邻数之间的差存一个数组 O(n)
然后再选择最大的k个差值 O(n)
总复杂度O(n) |
|
c********1
发帖数: 52 | 40
partition,最大是整个
我觉得我没把问题讲清楚。。。这个不是partition的问题
比如说给一个数组 [1,4,6,7] k = 2
那么我们选1和7就是最优的 因为差是6最大
如果k=3我们选1，4，7
差是3 (maximize the minimal difference) |
|
h*******s
发帖数: 8454 | 41 用vector of vector不是挺好么，为啥非要用数组
可以试试
template
void foo(int m[][width], int height); |
|
b******g
发帖数: 1721 | 42 大概的还不错。
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
用楼上的例子，你的算法要越界啊，是针对第一个数组arr1在第二次循环的时候。
|
|
C***y
发帖数: 2546 | 43 稍微改进一下：
1.直接sort原来的数组
2.从第一个元素开始，扫描当前元素a[i]后面的subarray (a[i+1] to a[n-1]，找和为
-a[i]的pair，因为是sorted，所以可以O（n-i)找到
复杂度应该还是O(n^2) |
|
S*******0
发帖数: 198 | 44 不如直接把tmp1放在hash table里，scan原来数组，看-a是否在table里 |
|
b******g
发帖数: 1721 | 45 是nlogn吧，tmp1的size仍然是等于原始数组的长度，n。 |
|
|
m*********0
发帖数: 46 | 47 这个方法不错，觉得本质上和hash table一个思路。如果integer是long的话，extra
space可能会非常大。
有个简单的想法，先分别sort两个数组，O(nlogn) + O(mlogm). 然后merge，需要O(m+
n).
found |
|
N**********d
发帖数: 9292 | 48 【 以下文字转载自 Programming 讨论区 】
发信人: NeedForSpeed (working~~~~~), 信区: Programming
标 题: 问个缺少逗号的数组赋值问题
发信站: BBS 未名空间站 (Sun Jan 15 17:05:58 2012, 美东)
源程序是：
#include
#include
using namespace std;
int main(int argc, char * argv[])
{
std::string m_ColumnName [] =
{
"str1",
"str2"
"last_one"
};
cout << m_ColumnName[0].substr(0,4) << endl;
cout << m_ColumnName[1].substr(0,4) << endl;
cout << ... 阅读全帖 |
|
q***y
发帖数: 236 | 49 给一个全正数的数组，大小为N。将其分成连续的K段。要求每段的和尽量平均。也就是
最大化最小段的和。这个DP公式怎么列啊？ |
|
l*********8
发帖数: 4642 | 50 O(N)
// 大小N的数组有 N-k个不同的数， 范围 0-N-1， 找miss
// 注意：跟楼主题目不同，我假设数字范围从0 -- N-1
vector FindMissingNumbers(vector & a)
{
vector missing;
for (int i=0; i
{
while (a[i]!=a[a[i]])
swap(a[i], a[a[i]]);
if (a[i] != i)
missing.push_back(i);
}
return missing;
} |
|
