java38、题目:有一个已经排好序的数组。现输入一个数要求按原来的规律将它插入数组中。
解法一: 可以使用二分查找的方式来找到插入位置,然后将元素插入到对应位置。
public static void insert(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
int insertIndex = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
insertIndex = mid;
right = mid - 1;
}
}
if (insertIndex == -1) {
insertIndex = arr.length;
}
int[] newArr = new int[arr.length + 1];
for (int i = 0; i < insertIndex; i++) {
newArr[i] = arr[i];
}
newArr[insertIndex] = target;
for (int i = insertIndex + 1; i < newArr.length; i++) {
newArr[i] = arr[i - 1];
}
System.out.println("插入后的数组为:" + Arrays.toString(newArr));
}
解法二: 可以使用插入排序的方式,从后往前比较,找到插入位置后将元素插入。
public static void insert(int[] arr, int target) {
int insertIndex = arr.length;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] > target) {
arr[i + 1] = arr[i];
} else {
insertIndex = i + 1;
break;
}
}
arr[insertIndex] = target;
System.out.println("插入后的数组为:" + Arrays.toString(arr));
}
使用示例:
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int target = 4;
insert(arr, target);
}
输出结果:
插入后的数组为:[1, 3, 4, 5, 7, 9]
以上两种解法都可以实现按照原来的规律将输入的数插入到已排序数组中。
原文地址: https://www.cveoy.top/t/topic/i4L7 著作权归作者所有。请勿转载和采集!