Leetcode Day 1 ｜704.二分法查找｜27.移除元素

71 阅读 0 评论 47 点赞

我是靠谱客的博主爱听歌海燕，这篇文章主要介绍Leetcode Day 1 ｜704.二分法查找｜27.移除元素，现在分享给大家，希望可以做个参考。

704.二分法查找

思路：采用二分法在一个有序数组里进行查找，要注意的是数组里的所有元素都应该是不相同的，有两种书写思路，一种是左闭右闭【left,right】,一种是左闭右开【left,right），两种的整体思路类似但是细节上存在差异。而我们在考虑临界情况的时候也只需考虑我们的临界值能不能取得到的问题，比如在左闭右开的情况下考虑left<right还是left<=right就去想因为不存在【1,1)，所以是left<right,其他以此类推。

1.左闭右开

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int right=nums.size();
        int left=0; 
    while(left<right)//[left,right]
    {
        int middle=(left+right)/2;
        if(nums[middle]>target)
        right=middle;
        else if(nums[middle]<target)
        left=middle+1;
        else
        return middle;

    }
    return -1;//未找到

    }
};

2.左闭右闭

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int right=nums.size()-1;
        int left=0; 
    while(left<=right)//[left,right]
    {
        int middle=(left+right)/2;
        if(nums[middle]>target)
        right=middle-1;
        else if(nums[middle]<target)
        left=middle+1;
        else
        return middle;

    }
    return -1;//未找到

    }
};

注意：在左闭右开的时候由于right的值我们默认为是取不到的，若以right=nums.size()，而不是right=nums.size()-1。

27.移除元素

思路：采用双指针法或是暴力法。对于双指针法，设置一对快慢指针，快指针向前搜锁，慢指针负责保存用来输出的数组内的元素的位置。如果fast指向的数不等于val，那么就把这个数复制到slow所指向的位置，slow++，否则slow不动，fast继续向后搜索，最后返回slow的值就是新数组的size。

暴力解法

暴力解法很好理解，看起来很简单但是写下来还是需要注意很多的细节。首先要注意的是，每次数组前移，size需要减一，而for循环里用的也应该是mysize而不是nums.size()。还有要注意的是，每次覆盖掉一个元素，i也需要--，因为i之后的所有元素都前移了，i如果不前移，i++之后就会跳过一个元素产生错误！

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int mysize=nums.size();
       for(int i=0;i<mysize;i++)
       {
           if(nums[i]==val)
           {
               for(int j=i+1;j<mysize;j++)
               {
                   nums[j-1]=nums[j];
               }
            mysize--;
            i--;
           }
       }
       return mysize ;

    }
};

快慢指针（yyds）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0;
        for(int fast=0;fast<nums.size();fast++)
        {
            if(nums[fast]!=val)
            {
                nums[slow++]=nums[fast];
            }
        }
        return slow;

    }
};