这个题我默认的数组是有序的，其实是没有关系的，即使是没有序可以排序（冒泡和选择我之前写过的）。
这个题的主要思想是：拿哪个要插入的数通过二分查找数组中比较，返回需要插入的位置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]+",");
}
}
}
}
|
|
收藏
淘帖
踩
虽然看不懂.
