代码随想录-数组

代码随想录

数组

数组--二分查找

题目：力扣题目链接

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1        

题解：

class Solution {
    public int search(int[] nums, int target) {
        int mid;
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]>target){
                right=right-1;
            }
            if(nums[mid]<target){
                left=left+1;
            }
        }
            return -1;
    }
}

解析：二分法前提：数组有序且元素唯一。

定义两个指针，一个指向第一个元素，一个指向最后一个元素。那么此时中间的元素mid是(left+right)/2。目标元素可能在中间元素左边或者右边，或者就是中间元素。如果是中间元素，直接返回中间元素下标即可，如果目标元素在中间元素左边，让右指针左移，此时，一轮过后，mid更加接近目标元素。

如果目标元素在中间元素右边，让左指针右移，此时，一轮过后，mid更加接近目标元素。在left<=right的范围内即可找到。否则left>right即没有找到该元素，数组中无该元素。

数组--移除元素

题目：力扣题目链接

给你一个数组 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。

题解：

class Solution {
    public int removeElement(int[] nums, int val) {
        int length=nums.length;
        for(int i=0;i<length;i++){
            if(nums[i]==val){
                for(int j=i+1;j<length;j++){
                    nums[j-1]=nums[j];
                }
                i--;
                length=length-1;
            }
        }
            return length;
    }
}

解析：暴力解法：两层for循环，首先遍历数组，如果发现数组中某下标对应的值等于目标值，则将此值删掉，删掉方法即让此元素之后的所有元素左移一个覆盖该值即可。之后指针左移，即i--；让数组总长度减一，遍历完整个数组，即得到最后的长度，完成此题。

数组--有序数组的平方

题目：力扣题目链接

给你一个按 非递减顺序 排序的整数数组 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]

题解：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] a=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            a[i]=nums[i]*nums[i];
        }
       Arrays.sort(a);
       return a;
    }    
}

解析：让原数组中的每个元素平方放入另一个新数组中，在对新数组中的元素进行排序即可。

数组--长度最小的子数组

题目：力扣题目链接

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

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

题解：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
     int left=0;
     int right;
     int sum=0;
     int result = Integer.MAX_VALUE;
     for(right=0;right<nums.length;right++){
         sum+=nums[right];
        while(sum>=target){
            result=Math.min(result,right-left+1);
            sum-=nums[left++];
        }
     }
     if(result>=Integer.MAX_VALUE){
         return 0;
     }
     return result; 
    }
}

图示：

解析：滑动窗口：定义左右两个指针，还有一个检验数组长度是否合法的Integer.MAX_VALUE，首先让左右指针指向数组第一个元素，一个for循环，让右指针不断遍历数组进行相加，计算出sum，然后sum和目标值进行比较，如果sum小于目标值，则不断遍历让元素顺序相加，如果发现了sum值大于等于目标值，则其中一个结果出现，如果合法，则局部结果出现，个数为right-left+1，由于不确定个数是否还可以缩小，此时让左指针出动，首先减去左指针指向的元素值，然后让左指针右移，此时，已经缩小了一个元素，查看是否sum仍然大于目标值，如果大于等于，则继续上一步操作，否则让右指针右移动，不断循环，最后，如果结果合法，即可得到最后结果。

注意：while和if的区别：两者都为判断语句，只不过是if是单次循环的，只判断执行一次，而while语句是一个循环语句，可以多次执行。

数组--螺旋矩阵II

题目：力扣题目链接

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

题解：

class Solution {
    public int[][] generateMatrix(int n) {
        int l=0,r=n-1,t=0,b=n-1;
        int[][] a=new int[n][n];
        int num=1,sum=n*n;
        while(num<=sum){
            for(int i=l;i<=r;i++){
                a[t][i]=num++;
            }
             t++;
            for(int i=t;i<=b;i++){
                a[i][r]=num++;
            }
            r--;
            for(int i=r;i>=l;i--){
                a[b][i]=num++;
            }
            b--;
            for(int i=b;i>=t;i--){
                a[i][l]=num++;
            }
            l++;
        }
        return a; 
    }
}

​ 图示：模拟法

解析：模拟法。按照从左到右，从顶到底，从右到左，从左到顶，如图式螺旋进行模拟。定义一个二维数组，在合法的范围内进行图示模拟，注意在从左到右结束，准备从顶到底模拟时，应该让t++，同理从右到左结束，准备从底到顶模拟时，应该让l++。