1.LeetCode27移除元素
- 题是晚上刷的，今天看发现第一天的题目只写了快慢指针法（见链接Day1），现补充练习实现相向双指针法。
- 分析：相向双指针法是指使用左右指针，左指针寻找需要移除的元素，右指针寻找不需要移除的元素，将其交换，会改变元素的相对位置，和我的代码差不多，我是使用的遍历数组和计数，然后惊奇的发现，应该不用计数哇，i的位置就是新数组长度哇，果然这个脑子不自觉的就会有多余的实现哈哈，现修改如下：
点击查看代码
public class Solution {
//计数+交换
public int removeElement(int[] nums, int val) {
int i=0;
int right=nums.length-1;
for (;i<right+1;i++){
if(right<0){
return i;
}
if(nums[i]==val){
nums[i]=nums[right];
nums[right]=val;
right--;
i--;
}
}
return i;
}
}
- 根据文章实现方法代码如下：
点击查看代码
public class Solution {
//相向双指针法
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;
}
}
2.LeetCode35搜索插入位置题目链接
- 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。 - 示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2 - 示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1 - 示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4 - 分析：数组是有序的，直接遍历会比较快，但是题目说明为时间复杂度O(log n)，那么思考二分法
需要考虑的情况：1.目标值在数组元素中找到 2.目标值在数组所有元素之前 3.目标值插入数组中 4.目标值在数组所有元素之后 - 我的代码（Java）：
点击查看代码
public class Solution {
//要求时间复杂度o(logn),nums中无重复元素
public int searchInsert(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]>target){
right=mid-1;
}else {
left=mid+1;
}
}
return right+1;
}
}
- 暴力解法（java）：
点击查看代码
public class Solution {
//时间复杂度o(n)
public int searchInsert(int[] nums, int target) {
int i=0;
for(int num:nums){
if(num>=target){
break;
}
i++;
}
return i;
}
}
- 左闭右开区间解法(java)：
点击查看代码
public class Solution {
public int searchInsert(int[] nums, int target) {
int left=0;
int right=nums.length;
while (left<right){
int mid=(left+right)/2;
if(nums[mid]==target) {
return mid;
}else if(nums[mid]>target){
right=mid;
}else {
left = mid + 1;
}
}
return right;
}
}
- LeetCode34在排序数组中查找元素的第一个和最后一个位置题目链接
-
给你一个按照非递减顺序排列的整数数组 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] -
分析：我的笨方法哈哈，使用左右指针来遍历数组，如左指针碰到大于或等于target则停止，如右指针碰到小于或等于target则停止，判断此时左指针和右指针以及他们指向的值是否符合，不符合则返回[-1，-1]；符合则进行判断范围，代码如下：
点击查看代码
public class Solution34 {
public int[] searchRange(int[] nums, int target) {
int[] result={-1,-1};
int left=0;
int right=nums.length-1;
while (left<=right){
while (left<=right&&nums[left]<target){
left++;
}
while (left<=right&&nums[right]>target){
right--;
}
if(left>nums.length-1||right<0||nums[left]>target||nums[right]<target){
break;
}
if(left>=right){
result=new int[]{right,left};
}else{
result=new int[]{left,right};
}
break;
}
return result;
}
}
- 看了文章讲解，应该是使用两次二分法来进行查找到左右，再进行分别判断各种情况，代码如下：
点击查看代码
public class Solution{
/**
* 寻找target在数组里的左右边界，有如下三种情况：
*
* 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
* 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
* 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
*/
public int[] searchRange(int[] nums, int target) {
int leftBorder=getLeftBorder(nums,target);
int rightBorder=getRightBorder(nums, target);
// 情况一
if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
// 情况三
if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
// 情况二
return new int[]{-1, -1};
}
public int getRightBorder(int[] nums, int target) {
int left=0;
int right=nums.length-1;
int rightBorder=-2;
while (left<=right) {
int mid=left+((right-left)/2);
if(nums[mid]>target) {
right=mid-1;
}else {
left=mid+1;
rightBorder=left;
}
}
return rightBorder;
}
public int getLeftBorder(int[] nums, int target) {
int left=0;
int right=nums.length-1;
int leftBorder=-2;
while (left<=right) {
int mid=left+((right-left)/2);
if(nums[mid]>=target) {
right=mid-1;
leftBorder=right;
}else{
left=mid+1;
}
}
return leftBorder;
}
}
- 总结：34题好像还有点晕乎乎，二刷时候再做做吧！还有一种是先二分法再滑动窗口的，等我学了再更！