黑马程序员技术交流社区
标题:
实现数组中插入一个数并实现有序，写得不好求改正。
[打印本页]
作者:
然后呢8908
时间:
2015-9-7 20:49
标题:
实现数组中插入一个数并实现有序，写得不好求改正。
这个题我默认的数组是有序的，其实是没有关系的，即使是没有序可以排序（冒泡和选择我之前写过的）。
这个题的主要思想是：拿哪个要插入的数通过二分查找数组中比较，返回需要插入的位置i（这里的位置需要仔细的分析一下，Arrarys.BianarySerach()这个函数，如果没有匹配的它的返回值是一个负值），然后可以重新建立一个数组，长度比原数组大1，
遍历新数组，给新数组赋值，原数组小于位置i的直接赋值给新数组，到了i把需要插入的书赋值给新数组位置i，然后把原数组后面的部分赋值给新数组（这里新数组的位置比原数组大1）.
import java.util.Arrays;
/*
* 面试题：
* 往一个有序的数组中插入一个数字
*/
public class ArrayDemo2 {
public static void main(String[] args) {
int[] arr={13,15,19,28,33,45,78,106};
int[] arr1=new int[9];
int a=11;
int index=halfSearch_2(arr,a);
System.out.println(index);
int index1=Arrays.binarySearch(arr, a);
int i=-(index+1);
for (int j = 0; j < arr1.length; j++) {
if (i==j) {
arr1[j]=a;
}else if (j<i) {
arr1[j]=arr[j];
}else {
arr1[j]=arr[j-1];
}
}
for (int j = 0; j < arr1.length; j++) {
System.out.println(arr1[j]);
}
}
public static int halfSearch_2(int[] arr, int key) {
int max,min,mid;
min=0;
max=arr.length-1;
while(min<=max){
mid=(min+max)/2;
if (key>arr[mid]) {
min=mid+1;
}else if (key<arr[mid]) {
max=mid-1;
}else {
return mid;
}
}
return -(min+1);
}
}
改进版：中间用到了Arrays的sort(),bianarySearch()方法和System的arrayCopy()方法。
并且是数组长度和元素自己定义，所以顺序要自己排。
import java.util.Arrays;
import java.util.Scanner;
/*
*
* 面试题：
* 往一个有序的数组中插入一个数字(之改进版)
*
*/
public class ArrayDemo {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
//定义数组的长度
System.out.print("请输入要输入的数组个数，n=");
int n=scanner.nextInt();
int arr[]=new int[n];
//定义数组并为数组赋值
System.out.print("请输入数组中的"+n+"个元素：");
for (int i = 0; i < arr.length; i++) {
arr[i]=scanner.nextInt();
}
System.out.print("请输入要插入的数：");
int num=scanner.nextInt();
Arrays.sort(arr);
//获取插入元素在原数组中的位置
int i= -(Arrays.binarySearch(arr, num)+1);
//复制数组并插入要插入的元素
int[] newArray=copyArray(arr,num, i, n);
//打印数组
print(newArray);
}
public static int[] copyArray(int[]arr,int num,int i,int n) {
int[] newArray=new int[n+1];
for (int j = 0; j < newArray.length; j++) {
if (i==j) {
newArray[j]=num;
}else if (j<i) {
System.arraycopy(arr, 0, newArray, 0, i);
}else {
System.arraycopy(arr,j-1, newArray,j,1);
}
}
return newArray;
}
public static void print(int[] arr){
System.out.print("[");
for (int j = 0; j < arr.length; j++) {
if (j==arr.length-1) {
System.out.print(arr[j]+"]");
}else {
System.out.print(arr[j]+",");
}
}
}
}
作者:
淡忘、悲年华
时间:
2015-9-7 20:51
虽然看不懂.
作者:
liyuan8
时间:
2015-9-7 20:53
很好,很好!!!
作者:
王乙帆
时间:
2015-9-7 20:53
666666666666666
作者:
silencea
时间:
2015-9-7 20:55
都到数组了..
作者:
Rzzz
时间:
2015-9-7 20:56
先mark 在慢慢看...
作者:
xiaoxiang_631
时间:
2015-9-7 20:56
虽然我也看不懂....
作者:
zhuchaofan
时间:
2015-9-7 20:59
改进版的冒泡排序,没看懂怎么办,要不要讲解一下.
作者:
0902赵建新
时间:
2015-9-7 21:07
虽然看不懂,但是我可以收藏啊.{:2_32:}
作者:
wuming668
时间:
2015-9-7 21:17
不错,挺好的.
作者:
heima_jinchen
时间:
2015-9-7 21:26
嗯呢,不赖不赖!!!
作者:
然后呢8908
时间:
2015-9-7 21:28
淡忘、悲年华 发表于 2015-9-7 20:51
虽然看不懂.
嗯，学到后面就都会了的，我现在主要是。。。你懂的
作者:
15706025762
时间:
2015-9-7 21:29
看不懂 --------
作者:
heimatai6
时间:
2015-9-7 21:59
好像还没学到这，我说咋看不懂呢
作者:
淡忘、悲年华
时间:
2015-9-8 21:19
然后呢8908 发表于 2015-9-7 21:28
嗯，学到后面就都会了的，我现在主要是。。。你懂的
懂,必须懂
作者:
淡忘、悲年华
时间:
2015-9-11 21:39
然后呢8908 发表于 2015-9-7 21:28
嗯，学到后面就都会了的，我现在主要是。。。你懂的
HMB.共同的追求
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2
虽然看不懂.