leetcode——数组

Posted on Edited on In Word count in article: 6.5k Reading time ≈ 6 mins.

前言

本部分记录，leetcode上面关于数组、二分查找等部分题目的思路，动态更新。

704. 二分查找

本题是典型的二分查找题目，题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int left = 0 , right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int num = nums[mid];
            if(num == target){
                return mid;
            }else if(num < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

复杂度分析

  • 时间复杂度：O*(log*n)，其中 n 是数组的长度。
  • 空间复杂度：O(1)。

35. 搜索插入位置

​ 还是二分查找，相对于704题来说，相当于多了一个额外的条件：即如果不存在数组中的时候需要返回按顺序插入的位置。

​ 这样问题可以转化为：在一个有序数组中找到一个大于等于target的下标

具体实现：和前面二分查找一样，但查找结束如果没有相等值则返回left，该值始终为需要插入的位置（至于为什么可以用几个实例理解一下）

或者利用下面方法理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0 , right = nums.length-1,ans = nums.length;
        while(left <= right){
            int mid = left+((right - left)>>1);
            if(target <= nums[mid]){
                ans = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return ans;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

想到一种比较好记忆的方法如下所示：

缺点在于：如果把int换成float，第四行代码的target+1就没法准确定义了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = searchIdx(nums,target);//找到第一个大于等于target的数
        int rightIdx = searchIdx(nums,(target+1))-1;//找到第一个大于等于target+1的数字，下标-1就是最后一个target的下标
        if(leftIdx==nums.length || nums[leftIdx]!=target ){//如果数组里面的数全都小于target，或者找到的第一个大于等于target的数不是target，则返回{-1，-1}
            return new int[]{-1,-1};
        }else{
            return new int[]{leftIdx,rightIdx};
        }

        
    }

    //和第35题一样的思路，找到第一个大于等于target的下标
    public int searchIdx(int[] nums, int target){
        int left = 0 , right = nums.length - 1, ans = nums.length;
        while(left <= right){
            int mid = (left+right)>>1;
            if(nums[mid] >= target ){
                ans = mid;
                right = mid-1;
            }else{
                left = mid +1;
            }
        }
        return ans;
    }
}

附上官方题解，其实相比于上面解法，定义的seach方法加了一个选择条件而已。推荐记忆理解下面这个解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);//查找第一个大于等于target的数
        int rightIdx = binarySearch(nums, target, false) - 1;//严格查找第一个大于target的数
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                //这里的if条件中有两个选择，开启了lower后，则查找第一个大于等于target的数，否则查找的是第一个大于target的数
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

209、长度最小的子数组

题目描述：给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0

示例：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路一：暴力求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int sum = 0;//总和
        int sublength = 0;//子数组长度
        for(int i = 0 ; i < nums.length ; i++){//起点为i
            sum = 0;
            for(int j = i ; j < nums.length;j++){//终点j不断增加
                sum += nums[j];
                if (sum>= target ){//如果发现了一个sum>target则j不继续往后扩，更新sublength
                    sublength = j - i + 1;
                    result = result < sublength ? result : sublength;//每次外循环判断更新的sublength是否最小
                    break;//跳出内循环
                }
            }
        }
        return result == Integer.MAX_VALUE ?0 :result;//如果一个没有则返回0
    }
}

/*执行用时：133 ms, 在所有 Java 提交中击败了12.68%的用户
内存消耗：41.1 MB, 在所有 Java 提交中击败了43.15%的用户*/

时间复杂度：O(n^2 )，其中 n是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。

空间复杂度：O(1)

思路二：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        //滑动窗口法
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for(int right = 0;right < nums.length ; right++){
            sum += nums[right];
            while(sum >= s){
                result = Math.min(result , right - left + 1);//判断本次结果和result哪个小
                sum -= nums[left++];//起始点右移
            }
        }
        return result == Integer.MAX_VALUE ? 0:result;
    }
}

209.长度最小的子数组

复杂度分析

  • 时间复杂度：O(n)，其中 n是数组的长度。指针start 和end 最多各移动 n 次。

  • 空间复杂度：O(1)。

59. 螺旋矩阵 II

这个题目按照题目要求模拟填入过程就可以了：

主要难点在于四个”指针”left、right、top、bottom之间的把控

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[][] generateMatrix(int n) {
        int left = 0 , right = n-1 , top = 0 , bottom = n-1 ;
        int[][] Mat = new int[n][n];
        int end = n*n;
        int num = 1 ; 
        while(num <= end){
            for(int i = left ;i <= right; i++){// left to right.
                Mat[top][i] = num++;
            }
            top++;
            for(int i = top ; i <= bottom; i++){// top to bottom.
                Mat[i][right] = num++;
            }
            right--;
            for(int i = right ; i >= left; i--){// right to left.
                Mat[bottom][i] = num++;
            }
            bottom--;
            for(int i = bottom ; i >= top; i--){// bottom to top.
                Mat[i][left] = num++;
            }
            left++;
        }
        return Mat;
    }
}