b******v
发帖数: 1493 | 1 可以用两个一维数组
a={0,2,3,1,3,6,6,2,5} 存储数据
b={0,3,7,9} 存储小数组的起始位置
原数组x[i][j] = a[b[i]+j] |
|
m********g
发帖数: 692 | 2 oops! 问的好...
思路:
1) 数组只有<=3个数, 答案
2)数组有4个数
这个懒的讲了
3)数组有>4个数
排序,
只有一个正数, 再找到最小2个负数 -- 答案
只有一个负数, 只需最大3个正数 -- 答案
否则
第三大正数拿出
最大2个正数
最小2个负数
比较乘积, 大的加上第三大正数就是答案.
如果没有第三大正数, 取最小的非正数
最小2个正数
除最小的非正数, 外最大2个负数
比较乘积, 小的加上 最小的非正数 就是答案. |
|
y**i
发帖数: 1112 | 3 这里我一直都不太懂，能指教一下吗？
如果key是每个数组的元素，假如说，数组的取值范围是从1-1000，数组大小是100，那
不是需要1000个hash的空间去存储？当然实际有值的空间<=100。如果要压缩空间，如
何压缩能解决碰撞问题？
关心它重复出现了多少次。 |
|
k*******d
发帖数: 701 | 4 1.取有序数组最大的那个作为size
2.n=size/8(假设一个int 8 位)个int数，值为0
3.然后遍历有序数组，根据有序数组元素的值k(假设为k)将相应n个int数的第k位值为1
,如果遇到重复数则跳过 |
|
l******e
发帖数: 6 | 5 int a1[] = {5,2,1};
int a2[] = {3,2,1};
用4个指针指向两个数组（头和尾分别是（5，2）和（3，2）），同时扫描连个数组并
比较大小，每
次只挪动一个尾指针；直到一个数组结束，再修改头指针。
void output(int* a1, int* a2, int* b, int n)
{
int count = 1;
b[0] = a1[0]+a2[0];
int i1(0), i2(0), j1(1), j2(1);
while (count < n)
{
if (a1[i1]+a2[j2] > a2[i2]+a1[j1])
{
b[count] = a1[i1]+a2[j2];
j2++;
if (j2 == n)
{
j2 = 1;
i1++;
}
}
else
|
|
g**********y
发帖数: 14569 | 6 对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
这个计算跟sliding window maximum是大同小异的。
如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。 |
|
g**********y
发帖数: 14569 | 7 对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
这个计算跟sliding window maximum是大同小异的。
如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。 |
|
w****o
发帖数: 2260 | 8 求两个数组的union 和intersection的时候，
如果数组里面有重复的数，在怎么处理？
比如 a[] = {3 2 5 7 8 5 6 5 9} //有三个5
b[]= {11 9 5 4 3 5} //有两个5
1. 最简单的方法，从a里取每个数a[i]，然后在b里做sequential search,看a[i]是否
在b里，这样的话，交集里面就会有三个5，
可是如果取b里的数，到a里面去找的，交集里会有两个5.
到底结果里应该有几个5?
同样并集里，有三个5还是两个5?
2. 如果先把a, b排序，然后用binary search的方法，也是有方法一里面的问题
3. 如果先把a, b排序，然后用两个指针，遍历两个数组，如果遇到两个数相同的话，
把两个指针都向前移动一步，这样的话可以避免上面的问题。
大家说说这个简单的问题该如何解决？
谢谢！ |
|
w****o
发帖数: 2260 | 9 你的这个方法，适合求并集， 复杂度是 m log m + n log n + m + n
可是你的方法，如何求交集？没有弄明白。
另外我觉得你的方法求并集的复杂度太高了。如果只把短的数组排序，用binary
search到短的数组中查找长数组里的数，这样的复杂度是 m log m + n log m (假设
m < n), 不过这个方法正像我在原帖里说的，没有办法处理重复的情形。 |
|
w****x
发帖数: 2483 | 10
设
这种merge的方法可以处理并集和交集吧. 而且可以处理重复情况
主要是编程简单.
对了, 你说的方法的确是一种优化, 可以通过分配一个和m一样大的数组来做记录, 记
录对应的index是否被访问过, 需要一种改进的binary search方法, 同时检查排序的小
数组和index 记录数组 |
|
w****x
发帖数: 2483 | 11 用hashtable保存value->index pair, 用bool数组记录对应index是否访问过, 遍历大
数组, 对每个值向两边延伸,更新hashtable和bool数组, 这样disjoint的segment就一
个个浮现出来了, O(n) |
|
h*********2
发帖数: 192 | 12 给个数组，打乱了，比如 索引 0 1 2 3 4 值 3 2 1 4 0 数组的值是下次跳的索引位
置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2 -> 1， 求最长环的长度.
这题咋做啊？
brute-force+ 记忆化？
问下大家~ |
|
l**********n
发帖数: 303 | 13 给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度. |
|
l**********n
发帖数: 303 | 14 给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度. |
|
y**3
发帖数: 12 | 15 我觉得可以先把数组变成链表，链表的每个Node保存其对应数组的下标和数值，然后用
一个最小化堆保存每个链表head node。
不断的弹出堆顶元素并且根据前后弹出来的堆顶元素的数值统计两两数组的相同元素个
数。 |
|
s*********3
发帖数: 25 | 16 我的想法是，把排序数组在左边镜像一下，镜像的那一般就都成负数了。
比方说原始数组是1， 3， 6， 9， 那变换之后成了 -9， -6， -3， -1， 1, 3， 6
， 9
这样就成了在排序数组中找两个数和为一个特定值。
就直接用两个指针前后开始走。
求拍。 |
|
T******7
发帖数: 1419 | 17 给一个数组， 找最大的整数m， 使得数组里比m大的或相等
的值的树木大于等于m（线性） |
|
发帖数: 1 | 18 给一个int[] data，数组大小最大100K
实现 int[] findIndices(long low, long upper)，返回值从小到大排序，同一个data
，findIndices会被执行多次
例：[100, 300, 25, 123, 3, 157, 9, 103, 304], findIndices(100, 200) 返回 [0,
3, 5, 7]
我想到就两种方法：
1：loop数组一个一个比较
2：排序成 [ {3, 4}, {9, 6}, {25, 2}, {100, 0}, {103, 7}, {123, 3}, {157, 5},
{300, 1}, {304, 8} ]，然后binary search low and upper，得到index的数组，再
排序这个结果，返回。如上面的列子，先得到 [{100, 0}, {103, 7}, {123, 3}, {157
, 5}]，拿indces，[0, 7, 3, 5]，再sort得到[0, 3, 5, 7]
2在极端的情况下会更慢，因为结果要再排序。
请教有没有更快的方法？ |
|
h*****n
发帖数: 209 | 19 【 以下文字转载自 Programming 讨论区 】
发信人: hanuman (神猴), 信区: Programming
标 题: 程序中的各个变量/数组的内存地址是否会混在一起?
发信站: BBS 未名空间站 (Sun Dec 19 01:03:09 2010, 美东)
比如说一个C程序内有很多int型的变量，还有一些int 或 char的数组，
有时候我发现这些变量的内存地址有可能和这些数组的地址混在一起了，这样就导致了
一些莫名其妙的bug。
不知道这是由于compiler的问题，还是程序本身没设计好。
我想版上的高手应该也经历过类似的问题。那么如何预防这种bug呢? |
|
I*******e
发帖数: 1879 | 20 ☆─────────────────────────────────────☆
chamberlain (PKU|PHY01|面朝大海|春暖花开) 于 (Thu Dec 14 17:53:04 2006) 提到:
怎样拷贝一个二维数组？
比如
double[][] matrix = new double[10][10]
然后对matrix的矩阵元赋值得到的数组，现在想将其复制到另一个数组里，怎么做？
当然比较笨的是用两个循环一个一个矩阵元的复制，但是有没有更好的方法呢？
今天写程序出错，才发现这个问题。本来写了如下一段代码
public class Matrix {
public double[][] m;
......
......
public Matrix replaceColomn(int colomnNumber, double[] newColomn) {
double[][] newMatrix = m.clone();
for(int i = 0; i < newMatrix.length; i+ |
|
b******y
发帖数: 9224 | 21 比如说，内存里有个very big array of integers. 开始用这个array的时候还好，但
如果有很长一段时间不reference这个数组了，貌似操作系统自动的把内存腾出来了，
也就是，这个数组进了disk 缓存区了。所以，有时候再次调用数组的时候，很慢。
有啥办法能够keep这种数据在内存中吗？
我想了一些办法，不过也想听听版上大牛们的建议。 |
|
c*****w
发帖数: 50 | 22 数组heap-sort，存储在数组中的heap ordered tree 不按level order而按pre order
如何实现？ Thanks！ |
|
c***d
发帖数: 996 | 23 ☆─────────────────────────────────────☆
hero (自古英雄出壮年) 于 (Thu Oct 11 21:09:47 2007) 提到:
提示，只便利一次，
not sort, no additional array memory.
进一步，有一个数组元素在数组中出现了>N/(k+1)次，请找出此元素。
☆─────────────────────────────────────☆
duz ( duz) 于 (Thu Oct 11 21:13:59 2007) 提到:
O(n)的算法，老题目啦
☆─────────────────────────────────────☆
raider (无所谓) 于 (Thu Oct 11 21:27:31 2007) 提到:
抽屉原理？
☆─────────────────────────────────────☆
liusand (R2D2) 于 (Thu Oct 11 23:23:08 2007) 提到:
N未知？
☆──────────────────────── |
|
w****h
发帖数: 212 | 24 一个方法，变量里需要定一个out 数组，如compose(int a, out int[] b)
方法内部需要初始化这个数组b
但问题是不知道数组b的长度，那么如何初始化b呢？ |
|
w****h
发帖数: 212 | 25 如果需要将arraylist生成的变长数组flow1复制到数组里，
double[] flow1_=(double[]) flow1.ToArray (typeof (double));
如果flow1_是二维数组，不知道如何复制？
flow1_[1,]＝(double[]) flow1.ToArray (typeof (double));吗？
那本书没讲。只好拿这里问 |
|
w****h
发帖数: 212 | 26 就是说，比如构造函数
class Point
{
Point (int x):myX(x) {};
private int myX;
}
那么程序可以直接定义Point u1(10)来定义这个实例u1,其myX=10
现在问题是，我想初始化类时传入一个数组，而不是一个整型变量，比如
class HeapSort
{
HeapSort (int* a):dataHeap(a) {};
public dataHeap[100];
}
当我定义
int a[N];
HeapSort h1(a)时，编译报错说cannot specify explicit initializer for arrays
是不是不能初始化就传入一个数组，而必须在函数里显示初始化数组 |
|
s***e
发帖数: 122 | 27 那就看你是要直接用传入的数组，还是你想内部克隆一个数组了。
在C/C++里面，普通数组的长度你必须自己知道，自己控制。如果你是用Java，那又另
说了。 |
|
d******a
发帖数: 238 | 28 来自主题: Programming版 - 数组问题
了解指针和数组差别的人也应该知道第二个原因啊。
当数组作为函数的参数进行传递时，数组就自动退化为同类型的指针啊。 |
|
i****d
发帖数: 255 | 29 // 定义二维数组的指针
double **zzz；
int i, j, irow = 100， icol = 4；
// 有两种方式malloc
// 第一种
zzz = (double**) malloc( sizeof(double) * irow * icol) );
for(i=0; i
zzz[i] = (double *) malloc( sizeof(double) * icol) );
// 第二种
zzz = (double**) malloc( sizeof(double*) * irow) );
for(i=0; i
zzz[i] = (double *) malloc( sizeof(double) * icol) );
*******************************************
感觉第二种方式好理解：先定义一个指针数组zzz[irow]；然后让里面的各个指针指向
一个个一维数组，即zzz[0]存储第0列的首地址，等等。
但第一种方式不好理解：感觉开辟了两份内存。
请指教！ |
|
c*******t
发帖数: 1095 | 30 我传了个全局数组到函数里，debug中在watch里面看所有值都是0，但实际运行当中用
到这个数组的时候是有值的，我看不到，这是什么原因？出了print还有其他办法能看到么？
如图，我的 gate_position[][2] 里面的值都是0，它怎么可能跳到if里面去的呢？但
按照我原来的传进来的值（因为是全局数组，我在函数里也能看到值）就是应该跳进去 |
|
f*******a
发帖数: 663 | 31 不矛盾啊，呵呵。
临时数组的变化如下：
[1 6 11]
[2 6 11]
...
[5 6 11]
刚才数组长度不一致忘说了，结束了就置一个NULL或者减少临时数组长度都可以
[6 11]
[7 11]
...
[10 11]
只剩一个的时候直接导入即可
[11]
基本思路而已，运算量不大。欢迎讨论 |
|
i**********e
发帖数: 1145 | 32 写了一个，如果是 k 个数组，每个数组长度最多是 N 的话，那么时间复杂度就是 O(
kN Log (k) )。需要空间复杂度 O(k) 来暂时储存暂时的 indices，来记录每个数组已
经进行到哪里了。
这个也可以用 divide and conquer，每次分半合并，递归解决。虽然时间复杂度是一
样的，但实际上肯定没有用 heap 快，因为递归的关系。
另一个变种就是 merge k sorted linked list，返回一个新的链表。这个就不需要额
外空间，可以每个 list 直接 advanced，指向每个链表进行的位置。但是编写起来很
麻烦，如果你不懂得点技巧的话。这个在 C++ 里用 double dereferencing pointer
代码可以写得相当简洁。
typedef pair Pair;
vector mergeKSortedArrays(vector > A) {
int k = A.size();
priority_queue, greater阅读全帖 |
|
k***t
发帖数: 57 | 33 有个全局数据 最开始定义的大小要比实际用到的大些
第一次循环对数组赋值
第二次循环想对数组重新赋值 长度仍然比定义的小 但会跟第一次循环时的长度不一样
这种情况请问如何重置数组啊？谢谢了 |
|
a***y
发帖数: 2803 | 34 memset是对char的数组赋值,如果是int 数组,用这个方法只能用于清零.
既然数组长度变化,可以用malloc分配动态空间,size也可变. |
|
X****r
发帖数: 3557 | 35 这几个函数各不相同。1的参数是对3x4的二维int数组的引用，2的参数是
指向3x4的二维int数组的指针，而3的参数是对长度为4的一维数组的指针，
因为函数形参出现T[]类型的时候会作为T*来处理。见C++ 2003 8.3.5
3. ... After determining the type of each parameter,
any parameter of type “array of T” or “function
returning T” is adjusted to be “pointer to T” or
“pointer to function returning T,” respectively.
比如
void func1(int (&array)[3][4]) {}
void func2(int (*array)[3][4]) {}
void func3(int array[3][4]) {}
int main() {
int array[3][4];
func1(array);
func2(&array);
func3(a... 阅读全帖 |
|
J********9
发帖数: 36508 | 36 需要处理大量数据
1.把数据写入临时binary文件 需要时读取
不过这样速度大大降低
2.用动态数组 速度大大提高 但是有virtual
memory问题 数组容量超过一定值 无论virtual
memory 设置多大都没法分配数组
请问如何解决？
谢谢 |
|
s*******g
发帖数: 243 | 37 你说的是java吧，因为java不支持自定义value type，所以List里存的都是
指针，customer可能分散在内存各个地方。C++ vector或者C# List存value type的话,
就能保证customer是连续存在一块内存里的。这样内存占用基本和三个数组没什么区别
了。
真正用起来快慢要看你干什么。如果你要求salary平均，当然是数组快，以为只需要读
一个数组。如果你要求每个customer的total income，就是用customer类快了。 |
|
l****r
发帖数: 105 | 38 最近没事刷刷leetcode，碰到几个二叉树问题，测试时创建二叉树手写起来太麻烦（C#
），所以想自己搞个工具，作用是根据给定数组创建二叉树。
初步写出来是这样的：
public static TreeNode CreateBinaryTree(int[] values)
{
TreeNode root = new TreeNode(values[0]);
Queue nodeQueue = new Queue();
nodeQueue.Enqueue(root);
TreeNode current = null;
foreach (var value in values.Skip(1))
{
if (current == null || (current.left != null && current.
right != null))
... 阅读全帖 |
|
y**i
发帖数: 44 | 39 现在需要fsolve解一个非线性方程，单独用另一个子程序m文件定义函数，不过函数的自
变量是一个数组，数组维数我将在主文件用input赋值，就是说，我现在需要在子程序里
面不赋初值的定义一个数组，用linspace和one(n,1)都不可以，也不需要symbolic的计算
，所以不能用syms,
该如何
在线请教各位高手，在下水平低劣，问题幼稚，见笑
感谢先 |
|
b*********n
发帖数: 1258 | 40 【 以下文字转载自 Programming 讨论区 】
发信人: babyfacenan (黑土), 信区: Programming
标 题: C++动态2维数组用什么数据结构比较好？
发信站: BBS 未名空间站 (Mon Jan 25 21:37:01 2010, 美东)
程序是这样的
有一个动态长度的vector
然后对这个vector做DP
想问问那个DP结果的2维数组用什么数据结构比较好？
谢谢 |
|
x****r
发帖数: 99 | 41 总结的很好啊，谢谢：P
不过好像有个小问题？
如果 n=2 的时候:
假设数组1是{3， 9} 数组2是{4， 6}
那你的解法里面median = (max(A[0], B[0]) + min(A[1], B[1])) / 2.0 = 6.5
而实际上应该是5
所以n = 2的时候还要讨论一下？
谢谢 |
|
w****l
发帖数: 88 | 42
举个例子，假设两个数组都只剩下2个元素，分别是： 1，4 和2， 5， 那么median
value 就是
（4+2）/2 =3. 不失一般性，假设两个数组剩下的元素分别为： a1, a2, b1, b2。 因
为两个数
组本身都是排号序的，那么必然有： a1 < a2, b1
相等）。 这
个时候如果进行merge， 得到的必定是如下几种情况：
1. a1, a2, b1, b2; (max(A[0], B[0])= b1,min(A[1], B[1])= a2)
2. a1, b1, a2, b2; 依次类推......
3. b1, a1, a2, b2;
4. b1, b2, a1, a2;
这4 种情况总结起来就是： (max(A[0], B[0]) + min(A[1], B[1])) / 2.0.
（本人新手，请轻拍：） |
|
a*******h
发帖数: 123 | 43 你的O(n)的算法其实用到了排好序的条件，当 i 找到不同上一次写入的元素的时候，根
据有序立马可以判断出这是一个没出现过的元素。
n)
设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描
过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度
也是O(n)。 |
|
y**i
发帖数: 1112 | 44 问个基本问题啊，如果用hash的话，空间需求是多少啊？
n)
设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描
过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度
也是O(n)。 |
|
j**l
发帖数: 2911 | 45 你的思路其实说到一种情况，就是已知取值的范围。这种情形也可以用数组（桶）来代
替Hash表的，每个Key直接作为下标去查找。比如对于ASCII字符，你用一个256大小的
数组就可以了。如果数值范围小，这种方法比Hash表还要快。但是这种方法可能会浪费
一些空间，而Hash表的好处就是只存储实际用到的元素。在PIE(Programming
Interview Exposed)一书中介绍Hash表的时候比较过了这两种方法。 |
|
j**l
发帖数: 2911 | 46 原来是要利用输出的数组b缓存辅助数组S和T的结果 |
|
f****4
发帖数: 1359 | 47 这道题目是求 N个元素数组中 N-1个元素最大积吧？
求连续元素最大乘积的，能用辅助数组解决么？
O(n)的是记录最大，最小乘积 |
|
r****o
发帖数: 1950 | 48 这个是编程之美中的一题，有谁有比较好的解法吗?
一个int数组，其中有3个majority数，每个都超过数组总数1/4。怎么找出这3个数来。
比如说3 2 6 3 2 1 6 3 6 2 7， 这3个数就是3,2,6 |
|
w******a
发帖数: 236 | 49 这道题可不可以用in-place merge sort来解？当然需要两个指针first, second，查找
后分别指向需要swap的两个已排序的子数组的起始点，比如：
1 6 7 2 3 4 5 8 k=2, n=7, a[0..k] sorted, a[k+1..n] sorted
那么first指向6，second指向5，将“6 7 2 3 4 5”段swap，然后“5 4 3 2”和“7 6
”swap, 得到“2 3 4 5 6 7”，最后数组排好序：1 2 3 4 5 6 7 8
确定first和second:
first=0;
while (first <=k && a[first] < a[k+1]) first++;
second=k+1;maxmove=0;
while (second <=n && a[second] < a[first]) {second++;maxmove++;}
swap(a,first,second);
swap(a,first,first+maxmove);
swap(a,second-(k-first+1),second);
可以进一 |
|
j*****u
发帖数: 1133 | 50 比qsort要快就是O(n)了，如果你知道“出现的次数”不超过某个值可以用基数排序
e.g.如果max=1M，开个1M的string array A，对keyword k如果出现n次，A[k] = n
scan一遍完就排好序了
如果有重复的，可以用数组或者链表作为数组中的元素 |
|
