package part1_basic;

import java.util.Arrays;

/*
有序数组插入元素：封装成方法

题目：有一个已经排好序的数组。现输入一个数，要求按原来的规律将它插入数组中。
*/
public class Ex028_arrayInsertElement_1 {
    public static void main(String[] args) {
        //获得排好序的数组：直接调JDK方法实现排序
        int[] arr = {0, 10, 1, 9, 3, 7, 4, 6, 2, 8};//0~10，缺少个5，等会就要插入一个5
        int num = 5;//需要插入的数

        //System.out.println(Arrays.toString(newArr));
        arr = arrayInsertNum(arr, num);//将新数组赋给旧数组
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 有序数组中插入一个元素，返回新数组
     *
     * @param arr
     * @param n
     * @return
     */
    public static int[] arrayInsertNum(int[] arr, int n) {
        Arrays.sort(arr);//排序，默认是升序排列

        //找出插入的元素在新数组的索引位置
        int oldLength = arr.length;
        int index = -1;//标记新元素的索引位置
        if (n < arr[0]) {//放在最前
            index = 0;
        } else if (arr[oldLength - 1] < n) {//放在末尾
            index = oldLength;
        } else {//在中间某个位置
            for (int i = 1; i < oldLength; i++) {
                if (arr[i - 1] <= n && n <= arr[i]) {
                    index = i;
                    break;//找到索引，就停下
                }
            }
        }

        //插入新元素：新数组放入元素
        int[] newArr = new int[oldLength + 1];//新数组
        for (int i = 0; i < newArr.length; i++) {
            if (i == index) {
                //新元素放好
                newArr[index] = n;
            } else if (i < index) {//新元素之前的部分，保持原索引不动
                newArr[i] = arr[i];
            } else {//新元素之后的部分，是原数组中的元素后移一位而来
                newArr[i] = arr[i - 1];
            }
        }
        return newArr;
    }
}

/*
分析：
    数组中插入元素，要注意以下几点：
    1.数组变长了，得新建一个新的数组存放所有的元素。
    2.插入的数在数组中哪个位置，得知道。
*/

package part1_basic;

import java.util.Arrays;

/*
有序数组插入元素：封装成方法

题目：有一个已经排好序的数组。现输入一个数，要求按原来的规律将它插入数组中。
*/
public class Ex028_arrayInsertElement_1 {
    public static void main(String[] args) {
        //获得排好序的数组：直接调JDK方法实现排序
        int[] arr = {0, 10, 1, 9, 3, 7, 4, 6, 2, 8};//0~10，缺少个5，等会就要插入一个5
        int num = 5;//需要插入的数

        //System.out.println(Arrays.toString(newArr));
        arr = arrayInsertNum(arr, num);//将新数组赋给旧数组
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 有序数组中插入一个元素，返回新数组
     *
     * @param arr
     * @param n
     * @return
     */
    public static int[] arrayInsertNum(int[] arr, int n) {
        Arrays.sort(arr);//排序，默认是升序排列

        //找出插入的元素在新数组的索引位置
        int oldLength = arr.length;
        int index = -1;//标记新元素的索引位置
        if (n < arr[0]) {//放在最前
            index = 0;
        } else if (arr[oldLength - 1] < n) {//放在末尾
            index = oldLength;
        } else {//在中间某个位置
            for (int i = 1; i < oldLength; i++) {
                if (arr[i - 1] <= n && n <= arr[i]) {
                    index = i;
                    break;//找到索引，就停下
                }
            }
        }

        //插入新元素：新数组放入元素
        int[] newArr = new int[oldLength + 1];//新数组
        for (int i = 0; i < newArr.length; i++) {
            if (i == index) {
                //新元素放好
                newArr[index] = n;
            } else if (i < index) {//新元素之前的部分，保持原索引不动
                newArr[i] = arr[i];
            } else {//新元素之后的部分，是原数组中的元素后移一位而来
                newArr[i] = arr[i - 1];
            }
        }
        return newArr;
    }
}

/*
分析：
    数组中插入元素，要注意以下几点：
    1.数组变长了，得新建一个新的数组存放所有的元素。
    2.插入的数在数组中哪个位置，得知道。
*/