随想录一刷·数组part1-摩杜云开发者社区

随想录一刷·数组part1_后端

你好，我是安然无虞。

文章目录

1. 二分查找题型
2. 移除元素题型

1. 二分查找题型

二分查找·传送门

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        // 在有序数组中查找第一时间想到二分查找
        int left = 0, right = nums.size() - 1; // 左闭右闭
        
        while(left <= right)
        {
            int mid = left + (right - left) / 2; // 防止溢出

            if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                return mid;
            }
        }

        return -1;
    }
};

题目拓展：

搜索插入位置

class Solution {
public:
  
  	// 注意对于本题的理解
    int searchInsert(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size(); // 左闭右开

        // 搜索左侧边界
        while(left < right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] == target)
            {
                // 收缩右侧边界
                right = mid;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid;
            }
        }

        return left;
    }
};

在排序数组中查找元素的左右边界

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        // 搜索左右边界
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);

        return {left, right};
    }

    // 搜索左侧边界
    int searchLeft(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1; // 左闭右闭

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] == target)
            {
                // 收缩右侧边界
                right = mid - 1;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
        }

        // 注意判断
        if(left >= nums.size() || nums[left] != target)
        {
            return -1;
        }

        return left;
    }

    // 搜索右侧边界
    int searchRight(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] == target)
            {
                // 收缩左侧边界
                left = mid + 1;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
        }

        if(right < 0 || nums[right] != target)
        {
            return -1;
        }

        return right;
    }
};

2. 移除元素题型

移除元素·传送门

class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针， fast在前面探路，遇到值不为val的元素就赋给slow
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};