算法学习第一天 | LeetCode704 二分查找、LeetCode27 移除元素

LeetCode 704 二分查找

题目链接: [704 二分查找](704. 二分查找 - 力扣(LeetCode))

思路:

  1. 根据有序数组、无重复元素条件基本可以判断使用二分法
  2. 确定区间的定义,一般分为两种写法,一种是左闭右闭即 left \leqslant target \leqslant right,另一种是左闭右开即 left \leqslant target < right

二分法第一种写法

定义 target 是在一个在左闭右闭的区间里,也就是[left, right]

要点:

  • while (left <= right) 要使用 <=,left = right的场景是有意义的
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target

代码如下:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= left) {
            int middle = left + ((right - left) / 2);
            if(nums[middle] > target){
                right = middle - 1;
            }else if(nums[middle] < target){
                left = middle + 1;
            }else{
                return middle;
            }
        }
        return -1;
    }
}

二分法第二种写法

定义 target 是在一个在左闭右开的区间里,**也就是[left, right)

要点:

  • while (left <= right) 要使用 <,left = right的场景是无意义的
  • if (nums[middle] > target) right 要赋值为 middle,因为右开区间不会去比较nums[middle]

代码如下:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(right > left) {
            int middle = left + ((right - left) >> 1);
            if(nums[middle] > target){
                right = middle;
            }else if(nums[middle] < target){
                left = middle + 1;
            }else{
                return middle;
            }
        }
        return -1;
    }
}

LeetCode 27 移除元素

题目链接: [27 移除元素](27. 移除元素 - 力扣(LeetCode))

思路:

  • 暴力破解
    两层for循环,外层for循环遍历数组元素 ,里层for循环更新数组。

代码如下:

// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};
  • 双指针法

要点:

定义快指针指向当前循环的nums下标,慢指针指向更新数组下标的位置

代码如下:

class Solution {
    public int removeElement(int[] nums, int val) {
        int lowIndex = 0;
        for(int fastIndex = 0;fastIndex < nums.length;fastIndex++){
            if(nums[fastIndex] != val){
                nums[lowIndex++] = nums[fastIndex];
            }
        }
        return lowIndex;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容