黑马程序员技术交流社区
标题:
一道数组合并题
[打印本页]
作者:
android0276
时间:
2014-7-2 16:32
标题:
一道数组合并题
本帖最后由 android0276 于 2014-7-6 20:26 编辑
已知两个有序数组A和B(升序),要求:数组C=AuB;已知A和B中元素的个数,分别为LenA和LenB,输出两个原数组且输出最后合并的结果数组。
本来想合并完排序好后,进行每个元素相同的比较,相同就继续循环,不相同就赋值,但是老是越界,我没想法了
作者:
海世山盟
时间:
2014-7-2 20:29
两个数组长度不一样,但是你都是用的同样的角标 肯定 短的一个会越界啊。
下面是没有排序的结果。你可以看看。代码没有优化。
public class addArr {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int[] arr1={1,2,3,4,5,6};
int[] arr2={3,4,5,6,76,87,34,2};
addArray(arr1,arr2);
}
public static void addArray(int[] arr1,int[] arr2){
List result=new ArrayList();
List list1=new ArrayList();
List list2=new ArrayList();
List maxList=new ArrayList();
List minList=new ArrayList();
for(int i=0;i<arr1.length;i++){
list1.add(arr1[i]);
}
for(int i=0;i<arr2.length;i++){
list2.add(arr2[i]);
}
maxList=list1.size()>list2.size()?list1 :list2;
minList=(maxList==list1)?list2:list1;
for(int i=0;i<maxList.size();i++){
result.add(maxList.get(i));
}
for(int i=0;i<minList.size();i++){
if(!result.contains(minList.get(i)))
result.add(minList.get(i));
}
System.out.println(result);
}
}
作者:
寐海流风
时间:
2014-7-2 20:55
数组操作最好还是用数组,效率:请楼主参考下哈
//求数组的并集
public static int[] arrayUnionLast(int[] arr1,int[] arr2){
String str = "";
int len = arr2.length;
for(int x=0;x<arr1.length;x++){
out:
for(int y=0;y<len;y++){
if(arr1[x]==arr2[y])
break;
if(arr1[x]<arr2[y]){
str += arr1[x]+" ";
break out;
}
}
}
String[] strArray = str.split(" ");
int[] arr = Arrays.copyOf(arr2,len+strArray.length);
for(int x=0;x<strArray.length;x++){
arr[len+x] = Integer.parseInt(strArray[x]);
}
Arrays.sort(arr);
return arr;
}
作者:
附耳细说
时间:
2014-7-3 01:34
涉及到一个算法
public static void main(String[] args) throws Exception {
int[] a = { 2, 5, 6, 7, 9, 12, 25 };
int[] b = { 0, 3, 4, 5, 6, 9, 11, 20 };
printArr(a);
printArr(b);
if (a[a.length - 1] > b[b.length - 1]) {
printArr(arrayCombine(a, b));
} else {
printArr(arrayCombine(b, a));
}
}
/**
* 打印数组
*
* @param arr
*/
private static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
/**
* 两个有序不含重复元素数组合成为一个有序不重复元素数组
*
* @param arrBig
* 数组最后一个值较大
* @param arrSmall
* 数组最后一个值较小
* @return 结果数组
*/
private static int[] arrayCombine(int[] arrBig, int[] arrSmall) {
// 合成数组的最大存储空间为arrBig.length + arrSmall.length,那就定义一个这样的数组空间
int[] arr = new int[arrBig.length + arrSmall.length];
int i = 0, j = 0, k = 0;
// 因为arrBig最后一个元素更大,所以肯定是arrBig最后复制进arr数组。也就是说arrSmall的索引指针i最先到达arrSmall的最后一个元素。
// 然后两个索引值对应的数组值比较大小,小的先存入arr中,同时合成数组和取值的数组索引值自增。
// 如果相等的话,三个数组索引值都自增,但是存储进合成数组的元素只有一个
while (i != arrSmall.length) {
if (arrBig[j] > arrSmall[i]) {
arr[k++] = arrSmall[i++];
} else if (arrBig[j] < arrSmall[i]) {
arr[k++] = arrBig[j++];
} else if (arrBig[j] == arrSmall[i]) {
arr[k++] = arrBig[j++];
i++;
}
}
// 这时候arrSmall 已经遍历完了数据,而arrBig中还有一段数组数据没有遍历过,直接把这段数据存储进合成数组
int arrBigLastLength = arrBig.length - j - 1;
arrayCopy(arr, arrBig, j, arrBigLastLength, k - 1);
// 把arr的冗余数据去掉
return arrayCopy(arr, 0, k + arrBigLastLength);
}
/**
* 带目标数组的数组复制
*
* @param dec
* 目标数组
* @param source
* 源数组
* @param startS
* 原数组开始索引位置
* @param length
* 从索引位置开始需要复制的长度值
* @param startD
* 目标数组开始的位置
*/
private static void arrayCopy(int[] dec, int[] source, int startS, int length, int startD) {
while (startS < length) {
dec[startD++] = dec[startS++];
}
}
/**
* 不带目标数组的数组复制
*
* @param source
* 源数组
* @param start
* 源数组开始索引的位置
* @param length
* 从索引位置开始需要复制的长度值
* @return 生成新数组
*/
private static int[] arrayCopy(int[] source, int start, int length) {
int[] result = new int[length - start];
for (int i = start; i < length; i++) {
result[i] = source[i];
}
return result;
}
作者:
附耳细说
时间:
2014-7-3 01:54
复制函数边界定义错了 ,重新发
public static void main(String[] args) throws Exception {
int[] a = { 2, 5, 6, 7, 9, 12, 25 };
int[] b = { 0, 3, 4, 5, 6, 9, 11, 20 };
printArr(a);
printArr(b);
if (a[a.length - 1] > b[b.length - 1]) {
printArr(arrayCombine(a, b));
} else {
printArr(arrayCombine(b, a));
}
printArr(arrayUnion(a, b));
}
/**
* 打印数组
*
* @param arr
*/
private static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
/**
* 两个有序不含重复元素数组合成为一个有序不重复元素数组
*
* @param arrBig
* 数组最后一个值较大
* @param arrSmall
* 数组最后一个值较小
* @return 结果数组
*/
private static int[] arrayCombine(int[] arrBig, int[] arrSmall) {
// 合成数组的最大存储空间为arrBig.length + arrSmall.length,那就定义一个这样的数组空间
int[] arr = new int[arrBig.length + arrSmall.length];
int i = 0, j = 0, k = 0;
// 因为arrBig最后一个元素更大,所以肯定是arrBig最后复制进arr数组。也就是说arrSmall的索引指针i最先到达arrSmall的最后一个元素。
// 然后两个索引值对应的数组值比较大小,小的先存入arr中,同时合成数组和取值的数组索引值自增。
// 如果相等的话,三个数组索引值都自增,但是存储进合成数组的元素只有一个
while (i != arrSmall.length) {
if (arrBig[j] > arrSmall[i]) {
arr[k++] = arrSmall[i++];
} else if (arrBig[j] < arrSmall[i]) {
arr[k++] = arrBig[j++];
} else if (arrBig[j] == arrSmall[i]) {
arr[k++] = arrBig[j++];
i++;
}
}
// 这时候arrSmall 已经遍历完了数据,而arrBig中还有一段数组数据没有遍历过,直接把这段数据存储进合成数组
int arrBigLastLength = arrBig.length - j;
arrayCopy(arr, arrBig, j, arrBigLastLength, k);
// 把arr的冗余数据去掉
return arrayCopy(arr, 0, k + arrBigLastLength);
}
/**
* 带目标数组的数组复制
*
* @param dec
* 目标数组
* @param source
* 源数组
* @param startS
* 原数组开始索引位置,包含
* @param length
* 从索引位置开始需要复制的长度值
* @param startD
* 目标数组开始的位置,包含
*/
private static void arrayCopy(int[] dec, int[] source, int startS, int length, int startD) {
for (int i = 0; i < length; i++) {
dec[i + startD] = source[i + startS];
}
}
/**
* 不带目标数组的数组复制
*
* @param source
* 源数组
* @param start
* 源数组开始索引的位置,包含
* @param length
* 从索引位置开始需要复制的长度值
* @return 生成新数组
*/
private static int[] arrayCopy(int[] source, int start, int length) {
int[] result = new int[length];
for (int i = 0; i < length; i++) {
result[i] = source[i + start];
}
return result;
}
作者:
EarlyHeart
时间:
2014-7-3 03:05
思路:1.利用Arrays.sort方法将所给数组排序。2.利用Set集合中元素的不可重复特性,帮助我们自动筛选重复元素
代码实现:
public static void main(String[] args) {
int[] a = {0,9,3,6};//数组a
int[] b = {-6,36,89,1,3,6};//数组b
//分别对数组a和b进行升序排序
Arrays.sort(a);
Arrays.sort(b);
//创建set集合,打算利用set集合元素的不可重复特性,筛选出两数组的并集
HashSet<Integer> set = new HashSet<Integer>();
for(int temp : a){
set.add(temp);
}
for(int temp : b){
set.add(temp);
}
//利用Set集合的toArray(T[] t)方法得到含有相同元素的int数组,并将其升序排序
Integer[] c = set.toArray(new Integer[0]);
Arrays.sort(c);
//打印结果
System.out.println(Arrays.toString(a));//[0, 3, 6, 9]
System.out.println(Arrays.toString(b));//[-6, 1, 3, 6, 36, 89]
System.out.println(Arrays.toString(c));//[-6, 0, 1, 3, 6, 9, 36, 89]
}
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2