代码随想录训练第一天|LeetCode704.二分查找、LeetCode34.在排序数组中查找元素的第一个和最后一个位置、LeetCode35.搜索插入位置、LeetCode27.移除元素
赞
踩
数组基础理论
数组是存放在连续内存空间上的相同类型数据的集合
数组的主要优势就是可以很方便的通过下标索引的方式获取到下标下对应的数据，在java中的应用一般是存放一系列对象的集合
如图所示
- 数组的下标都是从0开始
- 数组内存空间的地址是连续的
注意：数组的元素是不能删的，只能覆盖
正是因为数组在内存空间的地址是连续的，所以我们再删除或者添加元素的时候，就要移动其他元素的地址。
如上图，要删除下标为3的元素，需要对下标为3的元素后边的所有元素都要做移动操作
二维数组
如上图，二维数组也就是x，y轴相互交叉，类似与坐标轴的存储方式，将值存储在一个坐标上。
二维数组在内存的空间地址是连续的吗？
不同编程语言的内存管理是不一样的，C++中二维数组是连续分布的，而在java中则不是，java二维数组的每一行头结点的地址是没有规则的。应该是如下排列方式。
从图中可以看出，二维数组中的一维数组是连续的，而二维数组的头结点和尾节点并没有连续。
704.二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
- 1
- 2
- 3
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
- 1
- 2
- 3
提示：
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。
思路
使用二分法的主要条件有两个
- 数组为有序数组，如果不是有序数组的话，二分法查找也就没有了意义。
- 数组中没有重复元素，如果有重复元素的话，那么查找到的下标可能就不是唯一的了。
其次，最重要的是区间的定义，区间的定义就是不变量，在二分查找的过程中，保持不变量，在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
二分法区间的定义一般为两种，左闭右闭[left,right]，或者左闭右开[left,right)。
第一种解法（左闭右闭）
定义target是在左闭右闭区间内[left,right]内，这个很重要。
定义了左闭右闭区间，那么就可以确定两点。
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。在区间[left, right]中，left == right是有意义的。下标为right的值本身是在即将要遍历的区间内的。
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1。
//左闭右闭解法[left,right],也就是target定义在左闭右闭区间内 public int search(int[] nums, int target) { //定义左右下标 int left = 0; int right = nums.length -1 ; //因为从本质上将，每次范围的收缩不会改变left在right的左边的事实，如果left出现在right的右边，则代表已经遍历结束 while(left<=right) { //先确定二分点位置 int middle = (right-left)/2 + left; //如果此时二分点位置大于目标值，则将右下标修改为middle-1 //因为当前二分点一定不等于目标值，所以直接将右下标修改为middle-1 if(nums[middle]>target) { right = middle-1; } //如果此时二分点位置小于目标值，则将右下标修改为middle+1 //因为当前二分点一定不等于目标值，所以直接将左下标修改为middle+1 else if(nums[middle]<target) { left = middle+1; } else{ //返回目标值 return middle; } } return -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
- 29
时间复杂度：O(log n)
空间复杂度：O(1) 因为没有定义新的数组，所以空间复杂度不变
第二种写法
定义target是一个在左闭右开的区间里，也就是[left,right)，那么二分法的边界处理方式会发生改变
- while (left < right)，这里使用 < ,因为left == right，在区间[left, right)是没有意义的，其实我觉得主要原因是因为，下标为right的值本身是不在即将要遍历的区间内的。
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
public int search(int[] nums, int target) { //定义left int left = 0; //定义right 此时开始right就不在区间内了 int right = nums.length; while(left<right) { int middle = left+(right-left)/2; //此时如果目标值在左侧，向左收缩区间 if(nums[middle]>target) { right = middle; } //此时如果目标值在右侧，向右收缩区间 else if(nums[middle]<target) { left = middle+1; } else { return middle; } } return -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
时间复杂度：O(log n)
空间复杂度：O(1)
总结
主要要明确区间的定义，再循环中一定要坚持提前定义好的区间，然后再进行边界处理，也就是循环不变量规则。
34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
Related Topics - 数组
- 二分查找
思路
由于是连续数组，并且需求为时间复杂度为 O(log n) 的算法来解决该问题，因此可以采用二分查找的算法解决思路去解决该问题
- 首先采用二分查找找到目标值所在的下标
- 再采用向左遍历查找左边界，向右遍历查找右边界的方法来获得目标值在数组中的下标范围。
//采用二分法，实现数组的遍历。并且时间复杂度要为O(log n) public int[] searchRange(int[] nums, int target) { //定义左边界 int left = 0; //定义右边界 int right = nums.length - 1; int[] res = {-1, -1}; if(nums.length==0) { return res; } //当超出边界时退出循环 while (left <= right) { //定义中点 int middle = left + (right - left) / 2; //如果目标值小于中点值，则向左修改区间 if (nums[middle] > target) { right = middle - 1; } //如果目标值大于中点值，则向右修改区间 else if (nums[middle] < target) { left = middle + 1; } //此时已经找到了寻找的值，现在需要知道这个值的位置，从哪到哪 else { left = middle; right = middle; //向左遍历 while (true) { if (left - 1 > -1 && nums[left - 1] == target) { left--; } else { break; } } //向右遍历 while (true) { if (right + 1 < nums.length && nums[right + 1] == target) { right++; } else { break; } } res = new int[]{left, right}; break; } } return res; }
- 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
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
时间复杂度O(log n)
空间复杂度O(1)
35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
- 1
- 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
- 1
- 2
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
- 1
- 2
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
思路
首先是一个排序数组，其次无重复元素，最后是必须使用时间复杂度为 O(log n) 的算法。所以可以选择二分查找的方式进行解题。
- 首先用二分查找法找到是否存在这个元素，如果存在的话直接返回这个元素的下标就可以。
- 如果不存在这个元素，就可以直接返回当前left值，也就是元素插入的位置的索引值。
//采用二分法进行查找，查找完成后返回将要插入的位置即可 public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length-1; while(left<=right) { int middle = left+(right-left)/2; if(nums[middle]<target) { left = middle+1; } else if (nums[middle]>target) { right = middle-1; }else{ //找到了下标返回索引值 return middle; } } //没有找到下标，返回即将插入索引值 return left; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
时间复杂度O(log n)
空间复杂度O(1)
27.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
- 1
- 2
- 3
- 4
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
- 1
- 2
- 3
- 4
- 5
提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
Related Topics
-
数组
-
双指针
思路
要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
暴力解法
这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
删除过程如下：
很明显暴力解法的时间复杂度是O(n^2)，这道题目暴力解法在leetcode上是可以过的。
//暴力解法使用两层循环就可以完成任务，第一层循环遍历所有与元素，第二层循环用来移动元素 public int removeElement(int[] nums, int val) { int res = nums.length; for (int i = 0; i < res; i++) { //如果当前值等于目标值，则将当前值挪到最后边 if(nums[i]==val) { for (int j = i+1; j < res; j++) { nums[j-1] = nums[j]; } //当前元素已经被挪到后边去了，所以下一个遍历还是从当前元素开始遍历 i--; res--; } } return res; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
时间复杂度O(n^2)
由于没有定义新的数组,只定义了几个变量,所以空间复杂度O(1)
双指针法
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
删除过程如下：
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
*//**双指针法，使用快慢双指针，慢指针用来存放新数组的元素，快指针用来寻找新数组的元素，也就是不是目标值的元素
**
//双指针法，使用快慢双指针，慢指针用来存放新数组的元素，快指针用来寻找新数组的元素，也就是不是目标值的元素 public int removeElement(int[] nums, int val) { int slow = 0; int fast = 0; for (; fast < nums.length; fast++) { //如果找到目标值，则跳过当前循环，将fast指针指向下一个元素 //如果没找到，则将后一个元素向前移动 if(nums[fast] != val) { //将快指针的值赋给慢指针，相当于后边的元素向前移动 nums[slow]=nums[fast]; slow++; } } return slow; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
相向双指针法
相向双指针方法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
//相向双指针法，左指针用来寻找与目标值相等的元素，右指针用来寻找与目标值不等的元素 public int removeElement(int[] nums, int val) { //左指针 int left = 0; int right = nums.length -1; //当相向指针相交时退出循环 while(left<=right) { //当找到一个与目标值相等的元素时退出循环 while(left<=right&&nums[left]!=val) { left++; } //当找到一个与目标值不相等的元素时退出循环 while(left<=right&&nums[right]==val) { right--; } if(left<right) { //将有指针找到的不等于目标值的元素，赋予左指针找到的等于目标值的元素，最后再修改左右指针，进入下一循环 nums[left] = nums[right]; left++; right--; } } return left; }
- 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
