1.数组理论基础
数组是存放在连续存储空间中的相同类型数据的集合
二分法(力扣704.)
对于默认升序的数组,进行二分法搜索下标
-
易错点
-
while(left<right)还是(left<=right)
-
更新区间的时候,right=middle还是middle-1
-
-
左闭右闭写法
-
right = maxsize-1
-
while(left<=right)middle=(left+right)/2
-
if(nums[middle]>target)
-
right=middle-1
-
else if (nums[middle]<target)
-
left = middle +1;
-
class Solution {
public int search(int[] nums, int target) {
//左闭右闭
int left = 0;
int right = nums.length - 1;
if(target<nums[0]||target>nums[nums.length-1]){
return -1;
}
while(left<=right){
int middle = (left+right)/2;
if(nums[middle]<target){
left = middle + 1;
middle = (left+right)/2;
}else if(nums[middle]>target){
right = middle - 1;
middle = (left+right)/2;
}else{
return middle;
}
}
return -1;
}
}
-
-
左闭右开写法
-
right = maxsize
-
while(left<right)middle=(left+right)/2
-
if(nums[middle]>target)
-
right=middle
-
else if nums[middle]<target
-
left=middle+1
-
else return middle
-
return -1;
class Solution {
public int search(int[] nums, int target) {
//左闭右开
int left = 0;
int right = nums.length;
if(target<nums[0]||target>nums[nums.length-1]){
return -1;
}
while(left<right){
int middle = (left+right)/2;
if(nums[middle]<target){
left = middle + 1;
}else if(nums[middle]>target){
right = middle;
}else{
return middle;
}
}
return -1;
}
}
-
移除元素(力扣27.)
-
原始思路:由于题目中说元素的顺序可以改变;遍历数组,遇到想要删除的元素直接将数组最后一个元素赋值到此位置,并令数组长度自减;与此同时,最后一个元素也有可能是要删除的值,因此令循环的i自减,重新对此元素进行检查。
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
for(int i=0;i<len;i++){
if(nums[i]==val){
nums[i]=nums[len-1];
len--;
i--;
}
}
return len;
}
}
-
其实完成就是库函数erase :O(n)复杂度
-
双指针思路:此时顺序可以不变;定义快慢指针;快指针用来寻找正确的值,用来赋给慢指针指向位置;
-
slow=0
-
for(fast =0;fast<nums.size;fast++)
-
if(nums[fast]!=val)
-
nums[slow]=nums[fast]
-
slow++
-
return slow
-
class Solution {
public int removeElement(int[] nums, int val) {
//快慢指针,快指针剔除错误元素赋给慢指针指向的位置
int low = 0;
for(int fast = 0; fast < nums.length; fast++){
if(nums[fast] != val){
nums[low] = nums[fast];
low++;
}
}
return low;
}
}