LeetCode704题目链接:704. 二分查找 - 力扣(LeetCode)
第一时间的想法:
简单来说,二分法给我的印象就是想一条绳子上打很多的结,每次对折正好是一个结点,我们需要找到想要的结点比如(a)代码思路就是不断对折一直到绳子两端重合中间没有结点,最后剩下的就是要找的结点a了。
所以要使用是while循环来判断两端结点 数组左右闭区间(left<=right),左闭右开或者左开右闭就没有等于,每次中间值就等于两端之和的一半,当中间值在目标左边时,说明中间值比目标小,必须更改区间来往目标值靠近,所以要将左区间改为middle值的下一位。以此类推,在右边也是一样,当middle值和目标值一样时,直接输出即可。当left=right时,循环结束,还没找到说明目标值不存在,输出-1,
左闭右闭区间代码:
class Solution { public int search(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 -1; } }
左开右闭区间代码
class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right) while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 < int middle = left + ((right - left) >> 1); if (nums[middle] > target) { right = middle; // target 在左区间,在[left, middle)中 } else if (nums[middle] < target) { left = middle + 1; // target 在右区间,在[middle + 1, right)中 } else { // nums[middle] == target return middle; // 数组中找到目标值,直接返回下标 } } // 未找到目标值 return -1; } };
LeetCode35题目链接:35. 搜索插入位置 - 力扣(LeetCode)
思路:简单,不说了。
class Solution { public int searchInsert(int[] nums, int target) { int index=0; for(int i =0;i<nums.length;i++){ if(nums[i]<target){ index++; } } return index; } }
LeetCode27题目链接:27. 移除元素 - 力扣(LeetCode)
思路:用循环判断与val相同,相同跳过,不同后边取代前边实现移除;
一,暴力破解(双层for循环)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++) {
if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
for (int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
size--; // 此时数组的大小-1
}
}
return size;
}
};
二,双指针操作:
思路,慢指针充当index,快指针判断是否与val一致,不一致就是新数组要的。
class Solution { public int removeElement(int[] nums, int val) { int slow=0; for(int fast=0;fast<nums.length;fast++){ if(nums[fast]!=val){ nums[slow]=nums[fast]; slow++; } } return slow; } }
标签:right,target,LeetCode704,int,nums,随想录,middle,移除,left From: https://www.cnblogs.com/lengbo/p/17958909