代码随想录算法训练营第1天
今日任务
数组理论基础，704. 二分查找，27. 移除元素。
可选任务：35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置
链接：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY (opens in a new tab)
数组理论基础
确实比较基础，就当回顾了。
704. 二分查找
自己想法
想明白区间定义，固定一种模式写就ok。
遇到的问题主要是被python惯坏了，忘记分号、变量声明，直接编译不过也是醉了。
另外看题解，意识到移位操作也有点忘记了，需要review一下。
// 解法1：[left, right]
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
}// 解法2：[left, right)
class Solution {
public 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)
left = mid + 1;
else if (nums[mid] > target)
right = mid;
}
return -1;
}
}题解想法
略
困难
无，有的话就是忘记Java语法了。
回顾
-
移位操作
-
防止溢出的除法写法：
left + (right - left) / 2等同于(left + right) / 2 -
二分查找的区间定义：[left, right] 或 [left, right)
-
mid的考虑：本来有考虑算mid的时候，如果不能整除，上下取整有没有区别、会不会有问题。但是其实不会有问题，反正要和target比较的嘛。乃至于说，可以不取中间，随机找一个分界点都ok。毕竟只是题目叫“二分查找”，谁也没有规定不能三分、四分查找，就是效率差别而已，不要被题目限制思考。
27. 移除元素
自己想法
暴力遍历，复杂度O(n^2)
class Solution {
public int removeElement(int[] nums, int val) {
int index = 0, del_num = 0;
while (index <= nums.length - 1 - del_num) {
if (nums[index] == val) {
// 移动数组
int i = index;
while (i < nums.length - 1) {
nums[i] = nums[i + 1];
i += 1;
}
del_num += 1;
}
else
index += 1;
}
return nums.length - del_num;
}
}题解想法
快慢指针，复杂度O(n)
class Solution {
public int removeElement(int[] nums, int val) {
int slow_index = 0, fast_index = 0;
while (fast_index < nums.length) {
if (nums[fast_index] == val) {
fast_index += 1;
}
// 当fast_index指向的元素不等于val时，
// 将其赋值给slow_index指向的元素，
// 并且两个指针都向后移动一位
else {
nums[slow_index] = nums[fast_index];
slow_index += 1;
fast_index += 1;
}
}
return slow_index;
}
}相向双指针方法，复杂度O(n)，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素。
class Solution {
public int removeElement(int[] nums, int val) {
int left_index = 0, right_index = nums.length - 1;
while (left_index <= right_index) {
// 找最左边第一个等于val的元素
while (left_index <= right_index && nums[left_index] != val)
left_index ++;
// 找最右边第一个不等于val的元素
while (left_index <= right_index && nums[right_index] == val)
right_index --;
// 交换
if (left_index < right_index) {
nums[left_index] = nums[right_index];
left_index ++;
right_index --;
}
}
return left_index;
}
}其实相向双指针方法不一定需要找到right_index，大不了换过去发现是要删除的元素，下一轮再换right_index的左边一个就行。
class Solution {
public int removeElement(int[] nums, int val) {
int left_index = 0, rigth_index = nums.length - 1;
while(left_index <= rigth_index){
// 如果left_index指向的数组元素值等于val，那就交换
// 此时left_index还不++，因为不知道换来的是不是val
if(nums[left_index] == val){
nums[left_index] = nums[rigth_index];
rigth_index --;
}
else {
left_index ++;
}
}
return left_index;
}
}困难
无
回顾
-
快慢指针：两个指针一快一慢同时后移，快指针用于遍历，慢指针用于记录符合条件的元素。
-
相向双指针：有一点需要注意，内层while的判断条件，需要先写
left_index <= right_index，否则可能会出现数组越界的情况。
35. 搜索插入位置
自己想法
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else if (nums[mid] == target) {
return mid;
}
}
return left;
}
}题解想法
无
困难
无
回顾
easy，无
34. 在排序数组中查找元素的第一个和最后一个位置
自己想法
自己写的绕死了，虽然磕磕绊绊过了...
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int s_left = 0, s_right = right, e_left = 0, e_right = right;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 先找到一个等于target的index，然后在两边再找
s_right = mid;
e_left = mid;
while (s_left <= s_right) {
int s_mid = s_left + (s_right - s_left) / 2;
// 如果还等于，说明左边还有，则左边的right要往左移
if (nums[s_mid] == target) {
s_right = s_mid - 1;
}
else if (nums[s_mid] < target) {
s_left = s_mid + 1;
}
// 在循环结束前，s_left一定会等于s_right等于s_mid，
// 此时s_mid就是要返回的左边界，
// 但最后一个循环会导致s_right等于s_mid-1，而s_left依旧等于s_mid
// 故最终return的可以是s_left，也可以是s_right+1
// 另一边同理
}
while (e_left <= e_right) {
int e_mid = e_left + (e_right - e_left) / 2;
// 如果还等于，说明右边还有，则右边的left要往右移
if (nums[e_mid] == target) {
e_left = e_mid + 1;
}
else if (nums[e_mid] > target) {
e_right = e_mid - 1;
}
}
return new int[]{s_left, e_left - 1};
}
else if (nums[mid] > target) {
right = mid - 1;
}
else if (nums[mid] < target) {
left = mid + 1;
}
}
return new int[]{-1,-1};
}
}题解想法
// 力扣官方题解
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
return new int[]{leftIdx, rightIdx};
}
return new int[]{-1, -1};
}
// lower为真时，返回第一个target的index，
// lower为假时，返回第一个大于target的index
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)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
}// 自己写的，其中高亮行即为和普通无重复元素的二分查找不同的地方
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = binary(nums, target, true);
int right = binary(nums, target, false) - 1;
if (left <= right && nums[left] == target && nums[right] == target) {
return new int[]{left, right};
}
else {
return new int[]{-1, -1};
}
}
public int binary(int[] nums, int target, boolean first_loc) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right ) / 2;
if (nums[mid] > target) {
right = mid - 1;
}
else if (first_loc && nums[mid] == target) {
right = mid - 1;
}
else if (!first_loc && nums[mid] == target) {
left = mid + 1;
}
else if (nums[mid] < target) {
left = mid + 1;
}
}
return left;
}
}困难
- 在涉及重复元素的时候，边界条件不好判断
回顾
- 支持重复元素查找的二分查找实现