算法60天训练–9-6-day1

Problem:

思路

从题目中可以看出,数组中的元素是有序的,而且是不重复的,很满足二分法的使用条件,所以使用二分法来解决这道题,同时二分有两种情况,一种是左闭右闭,一种是左闭右开,而这两种情况在代码的形式上是不一样的.

解题方法

以right == left(两边顶点)为终止条件,根据左闭又开或左闭右闭来调整每一轮循环之后right和left两边端点的位置.始终将target在端点之间,直到right = left.

复杂度

• 时间复杂度: O(log n)
• 空间复杂度: O(1)

Code[JAVA]

class Solution {
    public int search(int[] nums, int target) {

        int left = 0, right = nums.length;

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

Code[C++]

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int left = 0;
        int right = nums.size()-1;

        while(left <= right){
            int middle  = left + ((right-left)>>1);

            if(nums[middle] < target){
                left = middle+1;
            }
            if(nums[middle] > target){
                right = middle-1;//右开
            }
           if(nums[middle] == target){
              return middle;
           }
        }
        return -1;
    }
};

Problem:

思路

首先可以两个for循环遍历.很简单

但是如果要减小时间复杂度,那么使用快慢指针

解题方法

首先定义两个指针fast,slow,如果fast指针指向的元素不等于要删除的元素,那么slow跟随fast一起往右移动,如果fast指向的元素等于要被删除的元素,那么slow不动,fast向右移动,直到fast->val不等于要被删除的元素,然后将其值赋值给slow指向的元素,如此循环,直到最右边,达到前面的等于2的元素被删除的目的.

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fastIndex = 0;
        int slowIndex = 0;

        for(fastIndex; fastIndex < nums.size(); fastIndex++){
            if(nums[fastIndex] != val){
                nums[slowIndex]  = nums[fastIndex];
                slowIndex++;
            }
            
        }
        return slowIndex;//移动几次说明有几个重复元素

    }
};