代码随想录算法训练营第一天｜LeetCode 704 二分查找、LeetCode 27 移除元素

数组相关知识点

数组是存放在连续内存空间上的相同数据类型的数据集合， 可以通过下标索引的方式获取对应的数据；由于数组在内存空间的地址是连续的，所以在删除或者增添元素的时候，就难免要移动其他元素的地址；

LeetCode 704 二分查找

解题思路

        题目中提到“在某一有序数组中查找某目标值的时候”应该联想到二分法——将目标值与某一区间的中间值进行比较，不断缩小搜索区间，得到最终答案。

        使用二分法的时候需要注意区间的定义（即区间是左闭右闭， 还是左闭右开）。因为不同的定义方法会影响left、right指针的初始化、循环条件的判定以及后续区间调整的策略。以初始化为例，区间是“右闭” 或者“右开” 时 right指针取值不同。

// 区间是左闭右闭

int left = 0;

int right = nums.size()-1;

// 区间是左闭右开：

int left =0;

int right = nums.size();

答案

1. 区间是左闭右开

class Solution{

public:

int search(vector &nums, int target)

{

// 左闭右开

int left = 0;

int right = nums.size();

while(left < right)

{

int middle = (left + right) /2;

if(nums[middle] > target)

{

// 右边取不到

right = middle;

}

else if(nums[middle] < target)

{

// 左边能取到, 即middle 肯定不在下一个区间中

left = middle+1;

}

else

{

return middle;

}

}

return -1;

}

};

LeetCode 27 移除元素

解题思路

        如果不考虑题目中的限制（“原地移除”， “不使用额外的空间”）， 最直接的做法应该就是初始化一个新的数组，遍历原数组，将不等于val的元素保存到新数组中。当然，这种做法也会有一些小坑，比如直接初始化数组的时候需要确定数组的长度，这需要先做一次统计，而且数组中元素不能直接删除，只能覆盖。

        本题比较好的解决方法是使用双指针法（快、慢指针）。

快指针：用来遍历数组；

慢指针：指向新数组的下一次更新的位置；

答案

1. 暴力解法

class Solution {

public:

int removeElement(vector& nums, int val) {

int size = nums.size();

for(int i=0; i

{

if(nums[i] == val)

{

for(int j=i+1 ; j

{

nums[j-1] = nums[j];

}

i--;

size--;

}

}

return size;

}

};

2. 快慢指针法

class Solution {

public:

int removeElement(vector& nums, int val) {

int slowIndex = 0;

for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {

if (val != nums[fastIndex]) {

nums[slowIndex++] = nums[fastIndex];

}

}

return slowIndex;

}

};

精彩内容

 您阅读本篇文章共花了：