黑马程序员技术交流社区

标题: 数组问题 [打印本页]

作者: 龚建锋 时间: 2012-7-8 13:50
标题: 数组问题
怎样在有序的数组中插入一个元素呢？并打印出来~~

作者: 陈冲 时间: 2012-7-8 13:56

static int[] insertArray(int a[], int key)
{
int i,j;
int b[];
i=a.length-1;
b=new int[a.length+1];//申请一个更大的空间
Arrays.sort(a);//使用java.util.Arrays.sort 方法对一个数组进行排序
//找到插入位置i
while(i>=0 && key<a[i])
i--;
if(i<0)
{
b[0]=key;
for(j=1;j<=a.length;j++)
b[j]=a[j-1]; //i<0说明key比a[]中所有值都小，所以插在数组最前面
}
else
{
for(j=0;j<=i;j++)
{
b[j]=a[j]; //a[0....i] copy 到b[0....i]
}
b[i+1]=key;
for(j=i+2;j<=a.length;j++)
b[j]=a[j-1];
}
return b;
}

复制代码

作者: 龚建锋 时间: 2012-7-8 14:09

陈冲发表于 2012-7-8 13:56

是不是相当于在折半查找法下进行插入操作呢~~

作者: 梁健生 时间: 2012-7-8 14:14

龚建锋发表于 2012-7-8 14:09
是不是相当于在折半查找法下进行插入操作呢~~

呵呵你说的很对，因为利用折半查找的前提条件就是数组为有序的，而所谓有序数组中插入元素，目前为止可以说等价于折半查找法下进行插入操作~~~！

作者: 刘美丽 时间: 2012-7-8 14:36
import java.util.*;
public class Text {

public static void main(String[] args) {

int[]num={1,3,4,6,7};
int s=2;
//将数组num和整数s传给Info作为参数并调用该方法
Info(num,s);
}

//定义一个有数组num1（即插入整数前的数组），有整数（该整数是要插入数组的数字）的参数的方法
public static void Info(int[]num1,int a){
//定义一个新数组，该数组比原数组的长度大1（因为插入的整数需要占用一个位置）
int[]num2=new int[num1.length+1];
//运用for循环将num1数组中的值赋给新数组num2；
for(int i=0;i<num1.length;i++){
num2[i]=num1[i];
}
//将插入的整数a放在新数组num2的最后一个位置
num2[num2.length-1]=a;//此时num2的数据是无序的
Arrays.sort(num2);//根据java的特有方法Arrays.sort()对num2的数据进行排序

//for循环输出排序后数组num2的值
for(int i=0;i<num2.length;i++){
System.out.println(num2[i]);
}
}
}

作者: 刘美丽 时间: 2012-7-8 14:42
import java.util.*;
public class Text {

public static void main(String[] args) {

int[]num={1,3,4,6,7};
int s=2;
//将数组num和整数s传给Info作为参数并调用该方法
Info(num,s);
}

  /*
定义一个有数组num1（即插入整数前的数组），有整数（该整数是要插入数组的数字）的参数的方法
*/
public static void Info(int[]num1,int a){

      int[]num2=new int[num1.length+1]; //定义一个新数组，该数组比原数组的长度大1（因为插入的整数需要占用一个位置）

         //运用for循环将num1数组中的值赋给新数组num2；
      for(int i=0;i<num1.length;i++){
            num2=num1;
         }
         //将插入的整数a放在新数组num2的最后一个位置
         num2[num2.length-1]=a;//此时num2的数据是无序的
         Arrays.sort(num2);//根据java的特有方法Arrays.sort()对num2的数据进行排序

         //for循环输出排序后数组num2的值
         for(int i=0;i<num2.length;i++){
               System.out.println(num2);
         }
   }
}

作者: 曹恒业 时间: 2012-7-8 15:02
怎样在有序的数组中插入一个元素呢？并打印出来~~
====================
其实这个问题毕老师视频里有讲解，只是没有实现插入的操作，因为数组插入操作不如链表效率高。
就这个问题而言，既然是有序数组（即使无序，用Array.sort();也能轻易实现）。那只要3步操作。
1.求出要插入的数据在新数组中的位置。即折半查找也好，依次比较也好。
2.将插入数据之后的原数组中的元素依次后移一格存入新数组。即脚标依次+1即可。
3.将排列好的新的元素顺序依次插入新数组。插入元素之前的元素脚标不变。
具体代码不难实现，希望楼主自己动手解决问题，加深印象。
就像毕老师所说，有些问题先想清楚具体步骤，再思考如何用代码实现，会比较简单。
希望帮到你了~~
作者: 黑马-李勇 时间: 2012-7-8 15:40
想法一：
1，建立一个比已知数组多一个元素的数组
2，将key插入到新数组的最后
3，对新数组排序Arrays.sort(b)
4，输出
import java.util.*;
class demo
{
public static void main(String[] args)
{
int [] arr={2,3,5,6,7,9};
int key=4;
insarr(arr,key);
}

public static void insarr(int[] arr,int key)
{
int [] b=new int[arr.length+1];//定义比arr多一个数的数组
b[arr.length]=key;//将key存到b数组的最后一位
for (int x=0; x<=arr.length-1;x++)//将arr拷贝到b数组中
{
b[x]=arr[x];
}

Arrays.sort(b);//对b排序
for (int x=0; x<=b.length-1;x++)//打印b数组
{
System.out.print(b[x]);
}
return;
}
}
想法二：
1，建立一个比给定数组多一个元素的数组，（给定为a，新的为b）
2，遍力a数组的每个元素，与key相比，写入b数组
   这里只有三种情况：
   a数组元素小于key，b数组［a数组脚标］值=a数组元素脚标值，
   a数组元素等于key，b数组［a数组脚标］值=key，b数组［a数组脚标+1］=a数组元素脚标值
   a数组元素大于key，b数组［a数组脚标+1］=a数组元素，
3，输出b数组
如有错，请指出{:soso_e113:}
作者: 黑马-李勇 时间: 2012-7-8 15:45
想法二有点问题，a数组中没有的。需要加个已经存入的标志。水平有限...

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2