704-二分法

題目鏈接：二分查找

關鍵問題：

????????- 邊界（left、right）、當前查找值（middle）

? ? ? ? ? ? ? ? - target大于當前查找值 --> 當前查找區(qū)域的右邊，更改區(qū)間left

? ? ? ? ? ? ? ? - target小于當前查找值 --> 當前查找區(qū)域的左邊，更改區(qū)間right

? ? ? ? ? ? ? ? - middle的計算 ：（right - left）/2? + left?

? ? ? ? - 查找區(qū)間

? ? ? ? ? ? ? ? - 開區(qū)間or閉區(qū)間 --> 涉及while的判斷條件即target不存在的情況

時空復雜度：

? ? ? ? - 時間復雜度：數(shù)組長度為n，查找區(qū)間的長度：n、n/2、n/4、n/8、...、n/2^k? --> O(log n)

? ? ? ? - 空間復雜度：O(1)

代碼

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)/2);
            if(nums[middle] == target){
                return middle;
            } else if(nums[middle] > target){
                right = middle - 1;
            } else{
                left = middle + 1;
            }
        }

        return -1;
    }
};

? ? ? ? 一些可以提升性能的細節(jié)：在三個if判斷中，將查找到結果放在最前(代碼第9-10行) --> 若當前命中則可以減少兩次判斷

27-?移除元素

題目鏈接：移除元素

1. 暴力解法

? ? ? ? 算法描述：當查找到每一個待刪除元素，都將所有后續(xù)元素向前移動一次

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 暴力解法 --> 所有元素前移
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(nums[i] == val){
                for(int j = i; j < n-1; j++){
                    nums[j] = nums[j+1];
                }
                i--;
                n--;
            }
        }
        return n;
    }
};

? ? ? ? 代碼細節(jié) （i--）：?由于發(fā)生了前移，當前位置i發(fā)生了元素的替換，而i在循環(huán)中自增，因此需要i--，回到位置i處。

? ? ? ? 時間復雜度：

2.快慢指針

? ? ? ? 算法描述：雙指針法，快慢指針同時從頭遍歷，遇到待移除元素時慢指針停止，快指針繼續(xù)移動直到遇到第一個不需要移除的元素，此時將快指針指向的元素拷貝到慢指針指向的數(shù)組位置，拷貝完成后，快慢指針繼續(xù)同步移動，直至快指針遍歷完數(shù)組。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //快慢指針
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++){
            if(nums[fast] != val){
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

????????時間復雜度：O(n)

3.相向雙指針

? ? ? ? 算法描述：雙指針法，設置首尾指針，首指針開始遍歷，當遇到待移除元素時停止，此時尾指針從后向前移動至不需要刪除的元素位置處，將尾指針指向的元素拷貝到首指針指向的位置，尾指針前移一步。首指針繼續(xù)遍歷，遇到待移除元素重復上述操作，直至首位指針相遇。

? ? ? ? 優(yōu)點：與快慢指針對比來考慮，若遇到待刪除元素在靠前位置時，快慢指針需要移動所有后續(xù)元素，而雙向雙指針只需要一次替換操作。舉例來說：對于數(shù)組A[n] = [0,1,1,...,1,1,2]，當需要刪除元素0時，快慢指針需要移動0后續(xù)的所有元素，得到的結果為A[n-1] = [1,1,...,1,1,2]，而相向雙指針僅需一次替換將2替換到最前，得到的結果為A[n-1] = [2,1,1,...,1,1]。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 相向雙指針
        int left = 0;
        int right = nums.size() -1;
        
        while(left <= right){// 閉區(qū)間
            if(nums[left] == val){
                if(nums[right] != val){
                    nums[left] = nums[right];
                    left++;
                }
                right--;
            }else{
                left++;
            }
        }
        return left;
    }
};

????????時間復雜度：O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-589111.html

到了這里，關于代碼隨想錄Day1 | 數(shù)組01- leetcode 704、27的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！