代码随想录1.5——数组：35搜索插入位置、34在排序数组中查找元素的第一个和最后一个位置、26.删除排序数组中的重复项、283移动零

1.35搜索插入位置 稍复杂，但是二刷通过

参考：代码随想录35搜索插入位置，力扣35: easy

1.1.题目

1.2.思路

注意这道题不是查找指定的元素，而是把元素按照顺序插入到数组中，因此和二分法查找稍有不同。但是实际上也可以使用二分法查找处理主要的逻辑，然后最后针对插入问题稍作处理即可。

1.3.暴力解法

在明白了上面的插入元素的不同情况之后，可以发现实际上插入的元素位置总是比它前面的元素大或者相等的，因此暴力解法直接找>=target的元素的第一个位置即可。

// 暴力解法：依次寻找待插入的位置，时间复杂度n
class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        // 处理三种情况：在数组最开头插入，在中间某个元素的位置插入，在中间两个元素之间的位置插入
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums.at(i) >= target)
            {
                return i;
            }
        }

        // 处理最后一种情况，在数组的最后插入
        return nums.size();
    }
};

1.4.二分法查找

题目给出的条件是有序数组、无重复元素，可见非常适合用二分法查找。但是由于这里是插入元素，因此还稍微有点不同。按照要插入的元素在数组中是否存在，可以分两种情况讨论：

1. 先假设我们要插入的元素在数组中就是存在的，那么此时这道题和二分法查找是一样的。
2. 如果说我们要插入的元素在数组中不存在，那么由上面的分析可以知道此时存在三种情况，即在数组最最前面插入、在数组最后面插入、在数组的两个数中间插入。如果我们先使用一个二分查找法，最后结果肯定是没有查找到target值，那么我们就可以分析一下如果是上面的三种插入情况，最后二分查找法返回的结果是怎么样的？即最后一个while(left <= right)结束之后，left、right和我们要插入的位置是不是有什么关系？

• target < nums[0], 此时left = 0, right = -1
• target > nums[last], 此时left = nums.size(), right = nums.size()-1
• target在某两个数之间，假设是nums[a]和nums[a+1]之间，那么遍历到left=a, right=a+1的时候，middle由于是向下取整，所以middle=a，也就是判断nums[a] < target，然后left=a+1。可以发现此时再次进入循环，因为left=right。然后middle=left=right, 此时判断nums[right]>target，然后right=middle，循环结束。最后left=a+1, right=a，而a+1就是要插入的位置。

可以发现，三种情况下，target插入的位置都是left的位置，因此循环到这里的时候，插入的位置就是left。

// 二分法查找，先寻找有没有这个元素，然后再处理插入的情况，时间复杂度log(n)
class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        // 使用左闭右闭的二分查找法
        int left = 0;
        int right = nums.size() - 1;
        
        while(left <= right)
        {
            int middle = left + (right - left)/2;
            if(nums.at(middle) == target)
            {
                return middle;
            }

            if(nums.at(middle) > target)
            {
                right = middle - 1;
            }    
            else
            {
                left = middle + 1;
            }
        }
        // 可以发现，三种情况下，target插入的位置都是left的位置，因此循环到这里的时候，插入的位置就是left
        return left;
    }
};

2.34在排序数组中查找元素的第一个和最后一个位置（有点复杂，思路不清）二刷没看，感觉对于二分法来说过于复杂

参考：代码随想录34在排序数组中查找元素的第一个和最后一个位置，力扣题目链接

2.1.题目

2.2.查找左右边界的思路

这道题乍一看其实是不满足二分法的条件的，因为二分法有两个条件，一个是需要非降序排列，一个是没有重复元素。但是这里的条件是有可能有重复元素，这样就导致二分法不能得到位移的解。

但是，本题是查找左右边界，实际上使用二分法可以查询重复元素出现的左右边界。比如nums = [1, 2, 3, 3, 3, 3, 4]，现在使用二分法查找3所在的左右边界。其实只需要把原来二分法调整边界的策略修改一下即可。

比如原来使用左闭右闭的标准二分法：

int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right)
{
    int middle = left + ((right - left) / 2);
    if (nums[middle] > target)
    { 
        right = middle - 1;
    }
    else if(nums[middle] < target)
    {
        left = middle + 1;
    }
    else   // 找到
    {
    	return middle;
    }
}

加入现在我们想找3的左边界，也就是nums中的第一个3。那么在使用标准二分法查找的时候，由于middle的计算，我们第一次不一定找到的是哪个3，比如如果nums中元素的总个数变化一下，那么我们第一次找到的3的位置不一定是哪个，如果使用标准的二分法，我们第一次找到3的时候就直接把他返回了，而无法确定是否是左右边界，以及如果不是再如何继续查找。

如何解决这个问题呢？假设我们第一次找到的是[1, 2, 3, 3, 3, 3, 4]中第三个3，并且我们想找到3的左边界，但是此时显然满足标准二分法中的else分支直接返回。然而我们想找3的左边界，所以此时我们应该修改代码，让else分支不是直接返回结果，而是继续把right向左移动一下， 此时nums变成[1, 2, 3, 3]，注意这里是左闭右闭区间，因此右边界right = middle - 1。然后再次查找，下次区间变成[3, 3]。然后再次查找，这次找到的是左边的3，同理我们还是想找左边界，然后继续向左找，即right = middle - 1。但是这时候发现，left指向的是第二个3，而right指向的是2了，因此不满足while循环了，退出。最终我们得到的right，就是3的左边界再左边的那个索引。

因此，要想找左边界，找到target之后也不能返回，而是应该把right继续向左移动，缩小包含target的区间，直到找不到target，此时的right就是左边界的再左边的那个索引。如果找右边界，则同理。

2.3.本题的解答

上面只是查找了左右边界，但是我们还需要对这道题进行分析，返回最后组合的[左边界，右边界]。

先给出代码，然后再分析上面的不同的左右边界情况：

class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        int left = getLeftBorder(nums, target);
        int right = getRightBorder(nums, target);
        if(left == -2 || right == -2)
            return {-1, -1};

        if(right - left > 1)
            return {left+1, right-1};

        return {-1, -1};
    }

private:
    // 寻找target在nums中的左边界
    int getLeftBorder(vector<int> &nums, int target)
    {
        // [left,right]二分
        int left = 0;
        int right = nums.size() - 1;
        // 注意为什么初始化成-2，因为一直在缩小的right就是我们求的左边界，如果根本不存在左边界，
        // 比如找在[1, 2, 3]中找5，那么left一直在变大，而right却是没有变化的。
        // 那么为什么要初始化成-2呢？初始化成-1行不行？答案是不行的，因为这个-2是在指示right到底有没有移动过，
        // 如果是在[1, 2, 3]中找-5，那么right一直减小，直到最后right
        int left_border = -2;    
        while(left <= right)
        {
            int middle = left + (right - left) / 2;
            if(nums.at(middle) >= target)
            {
                right = middle - 1;
                left_border = right;
            }
            else
            {
                left = middle + 1;
            }
        }

        return left_border;
    }

     // 寻找target在nums中的右边界
    int getRightBorder(vector<int> &nums, int target)
    {
        // [left,right]二分
        int left = 0;
        int right = nums.size() - 1;
        int right_border = -2;    
        while(left <= right)
        {
            int middle = left + (right - left) / 2;
            if(nums.at(middle) > target)
            {
                right = middle - 1;
            }
            else
            {
                left = middle + 1;
                right_border = left;
            }
        }

        return right_border;
    }
};

分析最终根据左右边界判断的情况：

1. [1, 2, 3]中寻找5的左右边界：

• 左边界：要不断左移right，直到不满足while循环。这种情况下显然right一直没动，left不断右移，因此最后left_border = -2
• 右边界：要不断右移动left，直到不满足while循环。这种情况下left不断右移，直到最后一个，所以right_border = 3(注意是3，不是2)

2. [1, 2, 3]中寻找-5的左右边界是类似的，左边界是-1，右边界是-2

3. [1, 2, 4]中寻找3：

• 左边界：左移right，从4移动到2结束，所以最后left_border = 1
• 右边界：右移left，从1移动到4结束，所以最后right_border = 2
  可见由于2和4中间不存在3，所以最后right_border - left_border = 1

4. [1, 2, 3, 4]中寻找3：

• 左边界：左移right，从4移动到2结束，所以最后left_border = 1
• 右边界：右移left，从1移动到4结束，所以最后right_border = 3
  所以最后right_border - left_border = 2 > 1

5. [1, 2, 3, 3, 3, 4]中寻找3：

• 左边界：左移right，从4移动到2结束，所以最后left_border = 1
• 右边界：右移left，从1移动到4结束，所以最后right_border = 5
  所以最后right_border - left_border = 4 > 1

3.26删除排序数组中的重复项 二刷AC

参考：力扣26: easy

3.1.题目

3.2.解答

这个题目和双指针移除元素的题目非常相似，就是一个稍微的变体。主要是因为本题已经给出了数组是非降序排列的，所以在判断是否有重复元素的时候，只需要备份前一个存储的元素，而不需要备份已经存储的所有元素。所以代码编程中就先设置一个最新的存储元素的备份值，然后用fast指针遍历原来的数组，只要遍历到的位置的数不等于最新的存储元素的备份值，那么他就不是重复元素，就可以存储它。

class Solution
{
public:
    int removeDuplicates(vector<int> &nums)
    {
        int slow = 0;
        int already_num = INT32_MAX;   // 已有的数，先备份成一个不在题目范围内的数

        for(int fast = 0; fast < nums.size(); fast++)
        {
            // 双指针，如果还没有这个数，那么才存到新的数组中
            if(nums[fast] != already_num)
            {
                already_num = nums[fast];
                nums[slow++] = already_num;
            }
        }
        return slow;
    }
};

4.283移动零 二刷AC

参考：力扣283: easy

4.1.题目

4.2.解答

这个和删除制定元素是一样的，每次存储都先把非零的元素存储起来，然后最后把零元素填充到数组的最后即可。

class Solution
{
public:
    void moveZeroes(vector<int> &nums)
    {
        int slow = 0;
        // 先把非零元素保存下来
        for(int fast = 0; fast < nums.size(); fast++)
        {
            if(nums[fast] != 0)
            {
                nums[slow++] = nums[fast];
            }
        }

        // 最后把后面的位置全部填充为0
        for(; slow < nums.size(); slow++)
        {
            nums[slow] = 0;
        }
    }
};