704.二分查找 27.移除元素

367 0 0

作者:zmak

LeetCode 704 二分查找

1.左闭右开

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

2.左闭右闭

public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

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

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

思路：

一（左闭右开）：因为是左闭右开的区间，rigth指针的位置为待查找数组的右边界下一个位置，所以当 left < right 的状态代表我们的数组还没查尽。

二（左闭右闭）：因为是左闭右闭的区间，rigth指针的位置为待查找数组的右边界位置，所以当 left <= right 的状态代表我们的数组还没查尽。

当我们对比了中间元素与目标的关系时，其实这时中间元素已经比较过了，我们要让我们的待查找数组把他排除在外，这也就是为什么 left = middle + 1 的原因（右边界不做举例，因为分了两种情况，其实都是一样，都是对待查找数组边界的控制）。

优化技巧：当我们最开始进入判断的时候，我们通过数组的递增性可以判断target是否数组最小值和大于数组最大值。将这种坏情况筛选出去。

LeetCode 27 移除元素

1.快慢指针

public int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if(nums[fastIndex] != val){
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }

思路：慢指针负责收集符合条件的元素，快指针负责查找符合条件的元素。当快指针查找到符合条件的元素交给慢指针，这时慢指针先前移动指向下一个元素（慢指针并不关心下一个元素是否符合条件，这时快指针做的事情，慢指针指向位置仅仅代表快指针查找到的下一个符合条件的元素要放到这里）。注意：当快指针查找到不符合条件的元素时，慢指针是不动的，快指针继续向前移动，去寻找符合条件的元素。

注：题目要求返回我们"整理"后的数组的新长度（符合条件的元素的个数），这正是慢指针的值，慢指针的值其实就是慢指针的移动次数，移动一次就代表收集了一个符合条件的元素。

2.相向双指针

public int removeElement(int[] nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex <= rightIndex){
            //从后向前寻找第一个不为val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val)
                rightIndex--;

            //从前向后寻找第一个为val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val)
                leftIndex++;

            if (leftIndex < rightIndex){
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;
    }

思路：我们使用后方不等于val的元素依次去替代前方等于val的元素。

注：特殊情况的考虑。

特殊情况：

当查找到最后left = rigth 的时候，如果nums[left] 等于val 这时直接返回left ，否则left需加一，同时又不能让替代语句影响我们的结果。这是

 while (leftIndex <= rightIndex && nums[rightIndex] == val)
                rightIndex--;

 while (leftIndex <= rightIndex && nums[leftIndex] != val)
                leftIndex++;

这两个while条件写法的原因所在。（这两个while语句并无先后顺序）

经过第一个while之后的可能：

第一种：找到了后方第一个不为val的值的索引。（该索引是有可能等于left的）

第二种（特殊）：该数组在 left 处以及 left 后全是val，这时应该停止查找了。因为我们已经得出答案，返回left就好了。（此时即使进入了最后一次循环，但是修改的是right的值，left是符合条件的）

经过第二个while之后的可能：

第一种：找到了前方第一个为val的值的索引

第二种（特殊）：该数组在 right 处以及 right 前全不是val，这时应该停止查找了。因为我们已经得出答案，返回left就好了。（因为进入了最后一次循环，这时left是比right大一的，符合全不是val的情况，直接返回left）

第三种：right 与 left的关系已经不符合条件了，代表该数组在 left 处以及 left 后都是val，我们要返回left

两个第一种情况用来逼近，逼近到发生特殊情况也就是两个第二种情况。

举例：{3} val = 1 这时符合第一种+第二种

　　　 {3} val = 3　　这时符合第二种+第三种

　　　 {3，2，2，3} val = 3 这时符合第一种+第一种来逼近，一直逼近到第一种+第二种

总结：相向双指针较难，以上分析极有可能出现错误，分析思路极有可能走弯路，欢迎大家指正。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/zmak/p/17619243.html

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

704.二分查找 27.移除元素