1. 27. 移除元素 (Remove Element)

題目要求：

給定數組 nums 和值 val，移除所有數值等於 val 的元素，返回移除後數組的新長度 k。要求原地修改數組，使得前 k 個元素為不等於 val 的元素。

解題思路：

  1. 使用雙指針的方法：一個指針遍歷數組，另一個指針標記不等於 val 的元素。
  2. 每次遇到不等於 val 的元素時，將其放置到前面的空位，並更新指針。
  3. 返回最後標記的不等於 val 的元素數量。

解題過程：

解法一：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();    //元素個數  
        int i = 0;
        while (i < n) {
            if (nums[i] == val) {
                for (int j = i; j < n -1; j++) {
                    nums[j] = nums [j + 1];
                }       //依次前移一位
                n--;    //去掉移動到最後的元素
            } else {
                i++;
            }
        }
        return n; //返回最終的元素個數
    }
};

//暴力移動

解法二：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int s = 0; //
        for (int f = 0; f < nums.size(); f++) {   //快指針遍歷
            if (nums[f] != val) {                  //查找非val元素
                nums[s] = nums[f];                 //快指針遍歷查到非val元素，慢指針才會前進-->慢指針停止前進則下一個一定是非val元素的存放地址；
                s++;                               //更換後再進行同步前進查詢，s++記錄非val元素個數
            }
        }
        return s;
    }
};

2. 704. 二分查找 (Binary Search)

題目要求：

在升序排列的整數數組 nums 中查找 target，若找到則返回其下標，否則返回 -1。要求時間複雜度為 O(log n)。

解題思路：

  1. 使用經典的二分查找方法：通過不斷縮小查找範圍，將目標與中間元素比較。
  2. 若目標等於中間元素，則返回該元素的下標。
  3. 否則，根據目標值與中間元素的大小關係更新左右邊界，繼續查找。

示例：

  • 輸入：nums = [-1,0,3,5,9,12], target = 9 → 輸出：4
  • 輸入：nums = [-1,0,3,5,9,12], target = 2 → 輸出：-1

約束條件：

  • 數組元素不重複
  • 數組長度 1 <= nums.length <= 10000
  • 元素值範圍 -9999 <= nums[i] <= 9999

解題過程：

解法一：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int sub = 0; //下標從0開始
        for (auto i : nums) { //auto i : nums --- i 直接指向nums中的元素
            if ( target == i) { //遍歷元素依次比對目標元素
                return sub;      //找到則返回下標值
            }
            sub++;       //本輪查詢未找到，循環查找下一個元素
        }
        return -1;    //循環結束未找到，則返回-1
    }
};

解法二：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //int i = nums.size() - 1;//size()返回值為元素個數，size()-1直接匹配下標
        for (int i=0; i < nums.size(); i++) {
            if ( nums[i] == target ) {
                return i;
            }
        }
        return -1;
    }
};

解法三：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i = 0,j = nums.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == target) {
                return m;
            }else if (nums[m] > target) {
                j = m - 1;
            }else {
                i = m + 1;
            }
        }
        return -1;
    }
};
//奇數：3個-->i=0.j=2,mid=(i+j)/2-->j=mid||i=mid;
//偶數：4個-->i=0,j=3,mid=(i+j)/2-->i=mid+1||j=mid;mid=(i+j)/2+1-->i=mid,j=mid-1
//不用考慮奇偶，不越界溢出即可

解法四：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i = 0, j = nums.size();
        while (i < j) {
            int m = i + (j - i) / 2;
            if (nums[m] > target) {   //左區間
                j = m;
            } else if (nums[m] == target) {
                return m;
            } else {
                i = m + 1;     //左區間
            }
        }
        return -1;
    }
};

3. 977. 有序數組的平方 (Squares of a Sorted Array)

題目要求：

給定一個非遞減順序排序的整數數組 nums，返回每個數字平方後按非遞減順序排序的數組。要求設計 O(n) 時間複雜度的算法。

解題思路：

  1. 使用雙指針方法：一指針從左邊開始，另一指針從右邊開始。
  2. 計算左右指針所指元素的平方，較大的平方先放入結果數組的末尾。
  3. 根據左右指針的比較，逐步填充結果數組。

示例：

  • 輸入：[-4,-1,0,3,10] → 輸出：[0,1,9,16,100]
  • 輸入：[-7,-3,2,3,11] → 輸出：[4,9,9,49,121]

約束條件：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按非遞減順序排序

解題過程：

解法一：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            nums[i]=nums[i]*nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

解法二：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector <int> newans(n);
        int i = 0, j = n - 1;
        for (int p = n - 1; p >= 0; p--) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                newans[p] = nums[i] * nums[i];
                i++;
            } else {
                newans[p] = nums[j] * nums[j];
                j--;
            }
        }
        return newans;
    }
};