w*********n
发帖数: 439 | 1 题目： 如果有一个二维数组 （包括两个以上一维数组 Arr1, Arr2, Arr3 ...)， 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array，不能用List等容器。
我的思路是：
1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2． 对每个一维数组中的元素进行从小到大排序，用的是快速排序方法 （quickSort).
3． 把第一个数组和第二个数组比较（我写了compare方法）生成共同元素的新数组，
然后把这个新数组依次和后面的每个数组比较，每次都生成新数组；
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候，在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code？不胜感激。
愿意的留个email吧。有包子 |
p*****2
发帖数: 21240 | 2 举个例子吧 没看懂问题
quickSort).
【在 w*********n 的大作中提到】
: 题目： 如果有一个二维数组 （包括两个以上一维数组 Arr1, Arr2, Arr3 ...)， 把
: 里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
: Array，不能用List等容器。
: 我的思路是：
: 1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
: 元素个数从小到大排列的。
: 2． 对每个一维数组中的元素进行从小到大排序，用的是快速排序方法 （quickSort).
: 3． 把第一个数组和第二个数组比较（我写了compare方法）生成共同元素的新数组，
: 然后把这个新数组依次和后面的每个数组比较，每次都生成新数组；
: 最后得到所有数组的共同元素的新数组。
|
g****s
发帖数: 1755 | 3 班门弄斧一下。
我的思路是可以在Linear时间内解决，先假定有N个Array，而且在每个Array中没有重
复的元素；
1. 做一个Hashmap，以Array[i]为Key，以该array[i]数值在全部N个Array中出现的次
数为Value；再做一个OutArray。
2. 从0到N-1遍历每个Array的每个数值，如果Hashmap里有这个数，则把
修正为.如果表里没这个数值，直接存。
3. 全部Array的全部元素都遍历结束后，任取一个Array0，就取第一个吧，遍历此
Array0，如果某个值array0[j],对应在hashmap里的Value是N-1的话，就说明这个数在
每个Array里都出现过，把这个数存到最终输出的数组OutArray里。
4. 输出OutArray；
=========
以下为简化的思路，无论单个数组里有无重复都可以用。
同样假定N个数组，同样初始化HashMap和OutArray；
1. 先把Array0里的数值放到HashMap里，Value全部设为1；
2. 从1到N-2遍历前面的N-2个数组；
对于第m个数组来讲，如果HashMap里没这个值，直接扔掉；如果ArrayM里的某个数
在HashMap里对应的Value为0或者小于m-1,扔掉这个值，如果对应的Value为m-1,则把该
Value修正为m+1,
3. 遍历最后一个数组；如果任意数值在Hashmap里对应该数的Value为N-1，则把该数值
存放到OutArray里，否则Check下一个数值。
4. 输出OutArray。
======
熬夜写作业，没有写Code验证，也不知我的思路有没有错误，见谅。 |
s*i
发帖数: 5025 | 4 1. Sort each
2. Scan from start of every sorted array for common elements
Time: n*m*log(m)
Or use hashset to get it down to n*m but not sure it is allowed to use
[发表自未名空间手机版 - m.mitbbs.com] |
l******t
发帖数: 55733 | |
s******y
发帖数: 416 | 6 把所有元素拷到一个临时array，出现二维数组行数次的为共同元素
quickSort).
【在 w*********n 的大作中提到】
: 题目： 如果有一个二维数组 （包括两个以上一维数组 Arr1, Arr2, Arr3 ...)， 把
: 里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
: Array，不能用List等容器。
: 我的思路是：
: 1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
: 元素个数从小到大排列的。
: 2． 对每个一维数组中的元素进行从小到大排序，用的是快速排序方法 （quickSort).
: 3． 把第一个数组和第二个数组比较（我写了compare方法）生成共同元素的新数组，
: 然后把这个新数组依次和后面的每个数组比较，每次都生成新数组；
: 最后得到所有数组的共同元素的新数组。
|
s***3
发帖数: 42 | 7 这样如果一维数组有重复元素就可能会有bug。
【在 s******y 的大作中提到】
: 把所有元素拷到一个临时array，出现二维数组行数次的为共同元素
:
: quickSort).
|
ET
发帖数: 10701 | 8 1, 2有啥区别。 都有quicksort了，1为啥还用bubble？
quickSort).
【在 w*********n 的大作中提到】
: 题目： 如果有一个二维数组 （包括两个以上一维数组 Arr1, Arr2, Arr3 ...)， 把
: 里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
: Array，不能用List等容器。
: 我的思路是：
: 1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
: 元素个数从小到大排列的。
: 2． 对每个一维数组中的元素进行从小到大排序，用的是快速排序方法 （quickSort).
: 3． 把第一个数组和第二个数组比较（我写了compare方法）生成共同元素的新数组，
: 然后把这个新数组依次和后面的每个数组比较，每次都生成新数组；
: 最后得到所有数组的共同元素的新数组。
|
ET
发帖数: 10701 | 9 他的问题描述的不清楚。 我的理解是这个n个array没有任何关系。
他只需要每单个1xn中的重复
【在 s*i 的大作中提到】
: 1. Sort each
: 2. Scan from start of every sorted array for common elements
: Time: n*m*log(m)
: Or use hashset to get it down to n*m but not sure it is allowed to use
: [发表自未名空间手机版 - m.mitbbs.com]
|
s*i
发帖数: 5025 | 10 的确有多种可能的解释。
貌似楼主已经作业 due 了，弃楼而去
[发表自未名空间手机版 - m.mitbbs.com]
【在 ET 的大作中提到】
: 他的问题描述的不清楚。 我的理解是这个n个array没有任何关系。
: 他只需要每单个1xn中的重复
|
|
|
s*i
发帖数: 5025 | 11 的确有多种可能的解释。
貌似楼主已经作业 due 了，弃楼而去
[发表自未名空间手机版 - m.mitbbs.com]
【在 ET 的大作中提到】
: 他的问题描述的不清楚。 我的理解是这个n个array没有任何关系。
: 他只需要每单个1xn中的重复
|
w*********n
发帖数: 439 | 12 非常感谢各位大侠的回答，还在为这道题操心。
如果每个一维数组里面都没有重复的元素，我写的方法可以做出来，但是现在一维数组
里面有重复的元素，就出空指针异常了。 |
w*********n
发帖数: 439 | 13 quickSort是对一维数组进行： quickSort(Comparable[] c)
bubbleSort是对二维数组进行：bubbleSort(Comparable[][] c)
【在 ET 的大作中提到】
: 1, 2有啥区别。 都有quicksort了，1为啥还用bubble？
:
: quickSort).
|
N********n
发帖数: 8363 | 14 It's piece of cake using Hash Table so why do they force you to use
arrays only. |
l**********n
发帖数: 8443 | 15 这个题是问怎么用array实现hashtable
【在 N********n 的大作中提到】
: It's piece of cake using Hash Table so why do they force you to use
: arrays only.
|
N********n
发帖数: 8363 | 16
If it's integer arrays then we can use 2 arrays to mimic hashT.
One array serves as the index. The other serves as the storage.
【在 l**********n 的大作中提到】
: 这个题是问怎么用array实现hashtable
|
c********g
发帖数: 449 | 17 要求用数组，但为什么对每个1维数组都排队呢？
可以只排序第一个，而后用其他数组的元素来查找第一个数组，根据是否找到来确定是
否有相同的元素，这样效率会高些吧？
假设 你已经做了“
1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
元素个数从小到大排列的。”
我来说个思路 看看 行不行：
1. 不需要对每个1维数组都排序，只排序第一个 Array1 并放入 ResultArray。
2.定义flag数组 并令 K=2
3. 用第 K 个数组的每个元素ArrayK2[j]去 折半搜索 ResultArray 找到则标记在
flag【i】=1 ，找不到 则flag【i】=0。
4.根据flag 来压缩ResultArray （去掉flag【i】=0的ResultArray【i】并记录 有效
数据的长度）
5 K=K+1，if （K<=N） goto 2.
6. ResultArray 含有结果（注意压缩后的有效数据的长度） |
N********n
发帖数: 8363 | 18
数组排序的效率是N*N*logN。用HASH是N*N。
【在 c********g 的大作中提到】
: 要求用数组，但为什么对每个1维数组都排队呢？
: 可以只排序第一个，而后用其他数组的元素来查找第一个数组，根据是否找到来确定是
: 否有相同的元素，这样效率会高些吧？
: 假设 你已经做了“
: 1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
: 元素个数从小到大排列的。”
: 我来说个思路 看看 行不行：
: 1. 不需要对每个1维数组都排序，只排序第一个 Array1 并放入 ResultArray。
: 2.定义flag数组 并令 K=2
: 3. 用第 K 个数组的每个元素ArrayK2[j]去 折半搜索 ResultArray 找到则标记在
|
c********g
发帖数: 449 | 19 算法时间复杂度分析：
设M个数组，最大数组长度为N
则：
1.排序M个数组的长度用 M*log（M）
2.排序第一个数组用时 <=N*Log(N)
3.用一个数组的所有元素来
检索数组1，用时<= N*Log(N)
M-1个数组则用 <= （M-1）*N*Log（N）
总的复杂度 <=M*log（M）+N*Log(N)+ （M-1）*N*Log（N）
<=M*Log(M)+M*N*Log(N)
Not too bad。
特例： if M=N/Log（N） 则 总的复杂度大约为 N*N。
【在 c********g 的大作中提到】
: 要求用数组，但为什么对每个1维数组都排队呢？
: 可以只排序第一个，而后用其他数组的元素来查找第一个数组，根据是否找到来确定是
: 否有相同的元素，这样效率会高些吧？
: 假设 你已经做了“
: 1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
: 元素个数从小到大排列的。”
: 我来说个思路 看看 行不行：
: 1. 不需要对每个1维数组都排序，只排序第一个 Array1 并放入 ResultArray。
: 2.定义flag数组 并令 K=2
: 3. 用第 K 个数组的每个元素ArrayK2[j]去 折半搜索 ResultArray 找到则标记在
|
p*****5
发帖数: 17 | 20 原题不清楚啊。
没有说数组里的元素可以排序吧，如果就只能equals，但没有implement comparator，
那就不能排序了。
所以还是hashtable 好，如果可以用的话 |
N********n
发帖数: 8363 | 21
其实用倆数组模拟一下DOUBLE-LINKED-LIST就可以实现数组版的HASHTABLE.
【在 p*****5 的大作中提到】
: 原题不清楚啊。
: 没有说数组里的元素可以排序吧，如果就只能equals，但没有implement comparator，
: 那就不能排序了。
: 所以还是hashtable 好，如果可以用的话
|
