不简单的数组增删改查（算法村第三关青铜挑战）

插人一个元素

题目描述

将给定的元素插入到升序数组的对应位置中，算法必须能保证在数组的首部、中间位置和尾部都可以插入成功。

先找位置再整体后移

先找位置，再将该位置后的元素整体右移，最后执行插入

/**
 * @param size 数组arr当前储存的元素个数，从1开始编号
 * @param element 待插入元素
 * @return index 插入位置的索引，从0开始编号。若数组已满，则返回-1
 */
public static int add_ordered(int[] arr, int size, int element)
{
    if(size >= arr.length)
        return -1;

    int index = size;   //element是递增数组的最大元素时，以下for循环无法找到正确位置，需要人工定位尾部位置

    //查找插入位置
    for (int i = 0; i < size; i++)
    {
        if (element < arr[i])
        {
            index = i;
            break;
        }
    }

    //腾出插入位置
    for (int j = size; j > index; j--)
        arr[j] = arr[j - 1];  //逐一往后覆盖，挪出位置

    //插入
    arr[index] = element;

    return index;
}

边找位置边后移

从后向前一边移动一边对比查找，找到位置直接插入。并不需要全部遍历，效率更好一些。

/**
 * @param size 数组arr当前储存的元素个数，从1开始编号
 * @param element 待插入元素
 * @return index 插入位置的索引，从0开始编号。若数组已满，则返回-1
 */
public static int add_ordered(int[] arr, int size, int element)
{
    if(size >= arr.length)
        return -1;

    int index = 0;  //element是递增数组的最小元素时，以下for循环无法找到正确位置，需要人工定位首部位置

    //腾出插入位置，索引size是尾部元素arr[i-1]要往后挪的位置
    for (int i = size; i > 0; i--)
    {

        arr[i] = arr[i - 1];  //从最后一个元素arr[i-1]开始追一后挪一个位置

        //经过模拟，i才是正确插入位置
        if(element > arr[i])
        {
            index = i;
            break;
        }
    }

    arr[index] = element;

    return index;
}

测试

public static void main(String[] args)
    {
        int[] arr = {1,2,2,4,5,7,9,0,0,0};  //7个元素
        int index;

        //插在首部,element = 0
//        index = addByElementSequence(arr,7,0);

        //插在中间,element = 3
        index = addByElementSequence(arr,7,3);

        //插在尾部,element = 10
//        index = addByElementSequence(arr,7,10);

        System.out.println(index);
        System.out.println(Arrays.toString(arr));
    }

删除一个元素

思路

因为元素可能不存在，所以不能从后向前一边移动一边查找。

只能分为两个步骤：

1. 先从最左侧开始查是否存在元素
2. 如果元素存在，则从该位置开始执行删除操作。

例如序列是1 2 3 4 5 6 7 8 9 ，若要删除5，则应先遍历找到5，然后从6开始逐步覆盖上一个元素，最终将序列变成 1 2 3 4 6 7 8 9 [9]

此时元素数量size会减1，从9变成8，原来9的位置仍然是9。由于我们通过size来标记元素数量，所以最后一个9不会被访问到。

Q：这个多余的9看起来很不爽啊，是否可以再优化一下？

A：不爽就不爽，习惯就好！不用优化，优化了也没啥用。

该方法同样要求删除序列最前、中间、最后和不存在的元素都能有效

代码

/**
 * @param size 数组中元素个数，从1开始记
 * @param key 待删除元素
 * @return size 执行删除操作后数组的元素个数。
 */
public static int remove(int[] arr, int size, int key)
{
    int index = -1;  //先假设数组中没有key值

    //查找删除位置
    for(int i = 0; i < size; i++)
    {
        if (arr[i] == key)
        {
            index = i;
            break;
        }
    }

    //若key存在，则从后往前覆盖删除
    if(index != -1)
    {
        for (int i = index + 1; i < size ; i++)
            arr[i - 1] = arr[i];

        size--;
    }

    return size;
}

测试

public static void main(String[] args)
    {
        int[] arr = {1,23,4,34,53,64,938};  //7个元素
        System.out.println("初始数组：");
        System.out.println(Arrays.toString(arr));

        int key = 0;
//        key = 1;    //删除第一个元素
//        key = 53;   //删除中间元素
//        key = 938;  //删除最后一个元素
//        key = 666;  //删除不存在的元素

        System.out.println("删除"+key);
        System.out.println("执行删除操作后的元素个数："+remove(arr, 7, key));
        System.out.println(Arrays.toString(arr));
    }

单调数列

题目描述

896. 单调数列 - 力扣（LeetCode）

如果数组是单调递增或单调递减的，那么它是 单调 的。

如果对于所有 i <= j，nums[i] <= nums[j]，那么数组 nums 是单调递增的。 如果对于所有 i <= j，nums[i]> = nums[j]，那么数组 nums 是单调递减的。

当给定的数组 nums 是单调数组时返回 true，否则返回 false。

示例 1：

输入：nums = [1,2,2,3]
输出：true

示例 2：

输入：nums = [6,5,4,4]
输出：true

示例 3：

输入：nums = [1,3,2]
输出：false

提示：

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105

直接判断法

public boolean isMonotonic(int[] nums)
{
    return isSorted(nums, true) || isSorted(nums, false);
}

public boolean isSorted(int[] nums, boolean isIncreasing)
{
    for (int i = 0; i < nums.length - 1; i++)
    {
        if (isIncreasing)   //判断是否为递增序列
        {
            if (nums[i] > nums[i + 1])
                return false;
        }
        else //判断是否为递减序列
        {
            if (nums[i] < nums[i + 1])
                return false;
        }
    }

    return true;
}

对比每组差值的符号

public boolean isMonotonic(int[] nums) {
           int diff=0;      //相邻元素的差
           int prediff=0;  //前一组相邻元素的差

           for(int i = 1; i < nums.length; i++)
           {
               diff = nums[i] - nums[i-1];
               
               //diff和prediff符号不同，即找到反例
               if(diff < 0 && prediff > 0 || diff > 0 && prediff < 0)
                    return false;
               
               //没有反例
               if(diff != 0)  //nums[i]-nums[i-1]不相同时
                    prediff = diff;  //更新
           }
           
           return true;
    }

二分查找搜索插入位置

题目描述

35. 搜索插入位置 - 力扣（LeetCode）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

/**
 * @param nums 递增序列
 */
public int searchInsert(int[] nums, int target)
{
    int index = nums.length;  //目标索引
    int left = 0;
    int right = nums.length - 1;

    while(left <= right)    //left = right 时判断最后一个元素
    {
        int mid = (left + right) / 2;

        if(target <= nums[mid])     //target = nums[mid]时，经过right = mid - 1,也达到条件left = right了，不需要break
        {
            index = mid;    //目标值的位置，或目标值应该插入的位置（动态维护）
            right = mid - 1;
        }
        else
            left = mid + 1;
    }

    return index;
}

合并两个有序数组

题目描述

88. 合并两个有序数组 - 力扣（LeetCode）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

**进阶：**你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

复制->排序

/**
* nums2复制到nums1，然后排序
*/
    public void merge(int[] nums1, int m, int[] nums2, int n)
    {
        for (int i = 0; i < nums2.length; i++)
            nums1[m + i] = nums2[i];

        //以上代码可替换为复制方法
//        System.arraycopy(nums2, 0, nums1, m + 0, nums2.length);

        Arrays.sort(nums1);
    }

O（m+n）

/**
 * 从后往前比较，然后把大的从nums1末尾位置依次往前放
 * @param nums1 非递减数组，同时也是合并后的数组
 * @param m nums1的元素数目
 * @param nums2 升序数组
 * @param n nums2的元素数目
 */
public void merge_2(int[] nums1, int m, int[] nums2, int n)
{
    int insert = m + n - 1; //插入位置
    int index_1 = m - 1;    //nums1的索引
    int index_2 = n - 1;    //nums2的索引

    while (index_1 >= 0 && index_2 >= 0)
    {
        if (nums1[index_1] >= nums2[index_2])
        {
            //把nums1[index_1]放到后面
            nums1[insert] = nums1[index_1];
            //调整索引，为下次比较和插入做准备
            index_1--;
            insert--;
        }
        else if(nums1[index_1] < nums2[index_2])
        {
            //把nums2[index_2]放到后面
            nums1[insert] = nums2[index_2];
            //调整索引，为下次比较和插入做准备
            index_2--;
            insert--;
        }
    }

    //处理剩余元素，并优化了相同逻辑的代码
    if (index_1 >= 0)
        while (index_1 >= 0)
            nums1[insert--] = nums1[index_1--];

    if (index_2 >= 0)
        while (index_2 >= 0)
            nums1[insert--] = nums2[index_2--];
}