LeetCode 27.移除元素
1. 数组理论基础
文章讲解：数组理论基础
1.1 什么是数组
数组：可以看成是相同类型元素的一个集合。在内存中是一段连续的空间。
- 数组中存放的元素其类型相同
- 数组的空间是连在一起的
- 每个空间有自己的编号，起始位置的编号为0，即数组的下标。
1.2 数组的创建及初始化
数组的初始化主要分为动态初始化以及静态初始化。
1.2.1 动态初始化：在创建数组时，直接指定数组中元素的个数
int[] array = new int[10];
1.2.2 静态初始化：在创建数组时不直接指定数据元素个数，而直接将具体的数据内容进行指定
int[] array1 = new int[]{0,1,2,3,4,5,6,7,8,9};
1.3 数组的使用
1.3.1 数组中元素访问
数组在内存中是一段连续的空间，空间的编号都是从0开始的，依次递增，该编号称为数组的下标，数组可以通过下标访问其任意位置的元素。比如：
int[]array = new int[]{10, 20, 30, 40, 50}; System.out.println(array[0]); System.out.println(array[1]); System.out.println(array[2]); System.out.println(array[3]); System.out.println(array[4]); // 也可以通过[]对数组中的元素进行修改 array[0] = 100; System.out.println(array[0]);
[注意事项]：
- 数组是一段连续的内存空间，因此支持随机访问，即通过下标访问快速访问数组中任意位置的元素
- 下标从0开始，介于[0, N）之间不包含N，N为元素个数，不能越界，否则会报出下标越界异常
1.3.2 遍历数组
所谓 "遍历" 是指将数组中的所有元素都访问一遍, 访问是指对数组中的元素进行某种操作，比如：打印。
int[]array = new int[]{10, 20, 30, 40, 50}; System.out.println(array[0]); System.out.println(array[1]); System.out.println(array[2]); System.out.println(array[3]); System.out.println(array[4]);
上述代码可以起到对数组中元素遍历的目的，但问题是：
- 如果数组中增加了一个元素，就需要增加一条打印语句
- 如果输入中有100个元素，就需要写100个打印语句
- 如果现在要把打印修改为给数组中每个元素加1，修改起来非常麻烦。
通过观察代码可以发现，对数组中每个元素的操作都是相同的，则可以使用循环来进行打印。
注意：在数组中可以通过 数组对象.length 来获取数组的长度
int[]array = new int[]{10, 20, 30, 40, 50}; for(int i = 0; i < array.length; i++){ System.out.println(array[i]); }
1.4 数组是引用类型
基本数据类型创建的变量，称为基本变量，该变量空间中直接存放的是其所对应的值；
而引用数据类型创建的变量，一般称为对象的引用，其空间中存储的是对象所在空间的地址。
1.5 二位数组
二维数组本质上也就是一维数组, 只不过每个元素又是一个一维数组.
1.5.1 基本语法
数据类型[][] 数组名称 = new 数据类型 [行数][列数] { 初始化数据 };
1.5.2 代码实例
int[][] arr = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; for (int row = 0; row < arr.length; row++) { for (int col = 0; col < arr[row].length; col++) { System.out.printf("%d\t", arr[row][col]); } System.out.println(""); } // 执行结果 1 2 3 4 5 6 7 8 9 10 11 12
2. LeetCode 704. 二分查找
2.1 自己的思路
- 因为自己前几天做了类似的题，也是二分法的，只不过要插入一个元素
- 当时自己对于二分法其实就是左右指针，一个0一个数组长度-1这样子，自己值得思考的问题就是以上的易错点，当时自己觉得这个left是小于还是小于等于right呢？也是思考了很久，因为以前听过，就凭借点记忆力直接小于等于然后下面的right=mid-1这样子，我自己是觉得理所应当的，但并不明白其中的逻辑。于是在看了carl哥的视频和文章才豁然开朗
2.2 易错点
- while()里是写left<=right还是left<right
- if(nums[mid]>target){}里是写right=mid-1还是right=mid
2.3 思路
2.3.1 左闭右闭写法：
- right=arr.length-1，因为是右边闭的，所以这么写能包含整个数组的值
- [1,1]合法区间，可以写成while(left<=right)，此时left<=right在区间里是有意义的
- 往下写if(nums[mid]>target){}里是right=mid-1还是right=mid呢？因为是右是闭区间，因为mid位置的值已经是大于target了，这个已经不是要找的值了，区间里还包括它就没有意义了。
- 举个极端的例子：如果边界可以取到mid的话，比如到了最后left=0，right=1，mid=0，如果target在1，left=middle还是会被设为0，middle永远取不到1，就死循环了
2.3.2 代码
class Solution { public int search(int[] nums, int target) { int left=0; int right=nums.length-1;//此时是左闭右闭区间，[left,right]，由于右区间有效，所以要-1 while(left<=right){//因为是左闭右闭区间，left==right是有意义的 int mid=(left+right)/2; if(nums[mid]==target){//找到target return mid; }else if(nums[mid]>target){//target在左区间 right=mid-1;// [left,mid-1] }else{//target在右区间 left=mid+1;// [mid+1,right] } } return -1; } }
2.3.3 左闭右开写法：
- right=arr.length，因为是右边开的，所以这么写能包含整个数组的值，写成arr.length-1的话就不能包含数组最右边的值
- [1,1)不合法区间，可以写成while(left<right)，此时若还是left<=right在区间里是没有意义的
- 往下写if(nums[mid]>target){}里是right=mid-1还是right=mid呢？因为是右是开区间，因为mid位置的值已经是大于target了，这个已经不是要找的值了，但又因为右区间是开的，所以包括进来是可以的
2.3.4 代码
class Solution { public int search(int[] nums, int target) { int left=0; int right=nums.length;//此时是左闭右开区间，[left,right)，由于右区间无效，所以不要-1，-1后就少了最右边的值了 while(left<right){//因为是左闭右开区间，left==right是无意义的 int mid=(left+right)/2; if(nums[mid]==target){//找到target return mid; }else if(nums[mid]>target){//target在左区间 right=mid;// [left,mid-1) }else{//target在右区间 left=mid+1;// [mid+1,right) } } return -1; } }
3. LeetCode 27. 移除元素
3.1 自己的思路&易错点
- 自己做这题时，想着用一个len记录数组原始长度
- 然后通过遍历找到目标值直接删除，然后len--直到所有的目标值删除
- 想着直接把数组上的值删除就行了
3.2 思路
3.2.1 暴力
- 这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
3.2.2 代码
class Solution { public int removeElement(int[] nums, int val) { int len = nums.length; for (int i = 0; i < len; i++) { if (nums[i] == val) { // 找到需要移除的元素，就将数组集体向前移动一位 for (int j = i + 1; j < len; j++) { nums[j - 1] = nums[j]; } i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位 len--; // 此时数组的大小-1 } } return len; } }
3.2.3 双指针
- 快指针是用来获取新数组中的元素（需要的元素，要删掉的不要），新数组就是不含有目标元素的数组（if ( nums[fast]!=val ) 不需要这个目标值，我们要删除掉）
- 慢指针是获取我们新数组中需要更新的位置（当 nums[fast]==val 时这是新数组不需要的那个目标值，此时快指针继续后移，慢指针停住）
- 但都是在一个数组中操作
3.2.4 代码
class Solution { public int removeElement(int[] nums, int val) { int slow=0;//慢指针是获取我们新数组中需要更新的位置 //快指针是用来获取新数组中的元素 for(int fast=0;fast<nums.length;fast++){ if(nums[fast]!=val){//只有fast上不是要移除的元素，才将fast上的值赋给slow，并且slow后移 nums[slow++]=nums[fast]; } } return slow; } }
3.2.5 双指针应用场景
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
4. 总结
4.1 时长
说来惭愧，这两题没那么难，但因为本人算法基础太差第二题没做出来，而且也是第一次写博客的原因，总耗时差不多2h17m。
4.2 心得体会
今天刷的题，带我自己复习了一下数组的内容，以及巩固了二分法的注意事项，还有双指针的一些应用场景，怎么使用等等，以及对于第二题暴力求解的思路也有很大感悟！希望自己能坚持下去，如果博客写的不好欢迎在评论区指正，你的指点是让我进步的最大帮助！
