代码随想录算法训练营第一天| 704. 二分查找、27.移除元素、977.有序数组的平方

704.二分查找

暴力法，耗时3：05

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++){
            if(nums[i] == target){
                return i;
           }
       }
        return -1;
   }
};

二分法，耗时10：39

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

主要是边界处理。要么定义为左闭友闭，要么是左闭右开。两种思路写法不同

27.移除元素

暴力法，耗时9：45

一开始没有让int size = nums.size();，然后超时了。

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--;
                size--;
           }
       }
        return size;
   }
};

双指针法：

看了解析之后写的，耗时2：02，目前是懂了双指针的思想了

快指针用来搜寻元素，慢指针用来更新数组下标位置。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for(int fastInddex = 0 ; fastInddex < nums.size() ; fastInddex ++){
            if(nums[fastInddex] != val){
                nums[slowIndex ++] = nums[fastInddex];
           }
       }
        return slowIndex;
   }
};

977.有序数组的平方

暴力法一下子就做出来了。

双指针法，看了解析

一个指针从前往后，一个指针从后往前

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j]) {
                result[k--] = A[j] * A[j];
                j--;
           }
            else {
                result[k--] = A[i] * A[i];
                i++;
           }
       }
        return result;
   }
};

今天到这。