Java数组常见算法LeetCode题

代码随想录的Java算法学习笔记

数组

数组是存放在连续内存空间上的相同类型数据的集合。

数组下标都是从0开始的，数组的元素是不能删的，只能覆盖

1.二分查找

前提是数组为有序数组且数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的

//测试
public class test01 {
    public static void main(String[] args) {
        int[] arr = {1, 4, 7, 9, 14, 17, 25, 29};
        int target = 1;
        int result = search(arr, target) + 1;
        if (result == 0) {
            System.out.println("数组中不包含这个数字");
        } else {
            System.out.println("查找的数字在数组中的位置为第" + result + "位");
        }
    }

    // 二分查找，左闭右开区间
    public static int search(int[] nums, int target) {
        //定义左右边界
        int left = 0, right = nums.length;
        while (left < right) {
            // 计算中间元素的索引
            int mid = (left + right)/2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                // target在右半部分，更新左边界
                left = mid + 1;
            else if (nums[mid] > target)
                // target在左半部分，更新右边界
                right = mid;
        }
        // 没有找到目标值，返回-1
        return -1;
    }
}
/*
时间复杂度：O(log n)
空间复杂度：O(1)
*/

2.移除元素（双指针）

//测试
public class test02 {
    public static void main(String[] args) {
        /* 给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
          不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
          元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
          示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 
          你不需要考虑数组中超出新长度后面的元素。
          示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5,
          并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
          你不需要考虑数组中超出新长度后面的元素。*/

        int[] arr = {3, 2, 2, 3};
        int val = 3;
        System.out.println(removeElement(arr, val));
    }

    // 快慢指针
    public static int removeElement(int[] nums, int val) {
        // 定义一个慢指针 slowindex，并初始化为 0
        int slowindex = 0;
        // 遍历数组 nums，i即为快指针
        for (int i = 0; i < nums.length; i++) {
            // 如果当前元素不等于 val
            if (nums[i] != val) {
                // 将当前元素赋值给慢指针位置的元素
                nums[slowindex] = nums[i];
                // 慢指针向后移动一位
                slowindex++;
            }
        }
        // 返回慢指针的值作为新的数组长度
        return slowindex;
    }
}
/*
 时间复杂度：O(n)
 空间复杂度：O(1)
 */

3.有序数组的平方（双指针）

//测试
public class test03 {
    public static void main(String[] args) {
        /*
         * 给你一个按非递减顺序排序的整数数组 nums，
         * 返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
         *
         * 示例 1：
         * 输入：nums = [-4,-1,0,3,10]
         * 输出：[0,1,9,16,100]
         * 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
         *
         * 示例 2：
         * 输入：nums = [-7,-3,2,3,11]
         * 输出：[4,9,9,49,121]
         */

        int[] nums = {-4, -1, 2, 3, 10};
        int[] arr = sortedSquares(nums);
        //强化for循环遍历数组
        for (int num : arr) {
            System.out.println(num);
        }
    }

    //双指针法
    /*
    数组其实是有序的， 只不过负数平方之后可能成为最大数了。
    那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
    此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
    定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
    如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j];
    如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i];
    */
    public static int[] sortedSquares(int[] nums) {
        //定义左指针 l，并初始化为 0
        int l = 0;
        //定义右指针 r，并初始化为数组长度减 1
        int r = nums.length - 1;
        //定义结果数组res，长度与nums相同
        int[] res = new int[nums.length];
        //定义结果数组的索引 j，并初始化为数组长度减 1
        int j = nums.length - 1;
        // 当左指针小于等于右指针时循环
        while (l <= r) {
            //如果左指针指向的元素平方大于右指针指向的元素平方
            if (nums[l] * nums[l] > nums[r] * nums[r]) {
                //将左指针指向的元素平方赋值给结果数组的当前位置，并将左指针向右移动一位
                //j--就是先使用j的数值再将j减小一位
                res[j--] = nums[l] * nums[l++];
            } else {
                //将右指针指向的元素平方赋值给结果数组的当前位置，并将右指针向左移动一位
                res[j--] = nums[r] * nums[r--];
            }
        }
        //返回结果数组
        return res;
    }
}
/*
时间复杂度：O(n)
*/

4.长度最小的子数组(滑动窗口)

滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

//测试
public class test04 {
    public static void main(String[] args) {
        /*
         给定一个含有 n 个正整数的数组和一个正整数 s，
         找出该数组中满足其和 ≥ s 的长度最小的连续子数组，
         并返回其长度。如果不存在符合条件的子数组，返回 0。
         示例：
         输入：s = 7, nums = [2,3,1,2,4,3]
         输出：2
         解释：子数组 [4,3] 是该条件下的长度最小的子数组。
         */
        int s = 7;
        int[] nums = {2, 3, 1, 2, 4, 3};
        System.out.println(minSubArrayLen(s, nums));
    }

    // 滑动窗口
    public static int minSubArrayLen(int s, int[] nums) {
        //定义左指针 left，并初始化为 0
        int left = 0;
        //定义和sum，并初始化为 0
        int sum = 0;
        //定义结果 result，并初始化为整数的最大值
        int result = Integer.MAX_VALUE;
        // 遍历数组 nums，右指针 right 从 0 到 nums.length-1
        for (int right = 0; right < nums.length; right++) {
            //将右指针指向的元素加到和 sum 中
            //sum += nums[right];等同于sum =sum+ nums[right];
            sum += nums[right];
            //当和sum大于等于s时循环
            while (sum >= s) {
                //更新结果 result，取当前子数组长度与 result 的较小值
                result = Math.min(result, right - left + 1);
                // 将左指针指向的元素从和sum中减去，并将左指针向右移动一位
                sum -= nums[left++];
            }
        }
        //如果结果 result 仍为整数的最大值，则返回 0，否则返回 result
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
/*
时间复杂度：O(n)
空间复杂度：O(1)
*/

5.螺旋矩阵II

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

坚持每条边左闭右开的原则

//测试
public class test05 {
    public static void main(String[] args) {
    /*
    给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，
    且元素按顺时针顺序螺旋排列的正方形矩阵。
    示例:
    输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
    */
        int[][] arrs = generateMatrix(4);
        for (int i = 0; i < arrs.length; i++) {
            for (int j = 0; j < arrs.length; j++) {
                System.out.print(arrs[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static int[][] generateMatrix(int n) {
        // 控制循环次数
        int loop = 0;
        int[][] res = new int[n][n];
        // 每次循环的开始点(start, start)
        int start = 0;
        // 定义填充数字
        int count = 1;
        int i, j;
        //判断边界后，loop从1开始
        //此处loop先进行比较再自增
        while (loop++ < n / 2) {
            // 模拟上侧从左到右
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }
            // 模拟右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }
            // 模拟下侧从右到左
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }
            // 模拟左侧从下到上
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++;
        }
        if (n % 2 == 1) {
            res[start][start] = count;
        }
        return res;
    }
}
/*
时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
空间复杂度 O(1)
*/