1.二分查找

704. 二分查找 - 力扣（LeetCode）

1.1 二分查找左闭右闭形式

例如, 数组为 [1,2,3,4,5,6],长度为6

left = 0, right = n -1;

我们在进行元素查找时可以让 left = right 取到右端点值进行比较的话可以采用 left<= right形式

  1. 如果是 左闭右闭形式,则right初始可以取到数组最后一位元素,则就是 right = n - 1;

    while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=

  2. 既然选择左闭右闭形式,则使用 while (left <= right);

  3. 在循环时,如果 arr[middle] > targht,更新右边界时,应该令 right = middle-1,因为选择了右闭， 如果 arr[middle] > targht, 则一定不会相等,再让 right = middle 也没意义,则选择 middle - 1;

  4. 左闭则同理,令 left = middle + 1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 2;
    int arr[n];

    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    int targht;
    cin >> targht;
    int left = 0;
    int right = n - 1;

    // [1,2,3,4,5]
    while (left <= right)
    {
        int middle = (left + right) / 2;
        cout << middle << endl;
        if(arr[middle] > targht) {
            right = middle -1;
        }
        else if(arr[middle] < targht) {
            left = middle + 1;
        }
        else if (arr[middle ] == targht) {
            cout << middle  << endl;
            break;
        } else {

        }
    }

    return 0;
}

1.2二分查找的左闭右开形式

例如, 数组为 [1,2,3,4,5,6],长度为6

left = 0, right = n;

我们在进行元素查找时不可以让 left = right 取到右端点值进行比较,则可以采用 left< right形式

  1. 如果是 左闭右开形式,则 right 初始 不可以 取到数组最后一位元素,则就是 right = n ;
  2. 既然选择左闭右开形式,则使用 while (left < right);
  3. 在循环时,如果 arr[middle] > targht,更新右边界时,应该令 right = middle
    ，因为右开，始终的范围是 right前面的，不包含right，则可以使right = middle
  4. 左闭令 left = middle + 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 2;
    int arr[n];

    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    int targht;
    cin >> targht;
    int left = 0;
    int right = n;

    // [1,2,3,4,5) 
    while (left < right)
    {
        int middle = (left + right) / 2;
        cout << middle << endl;
        if(arr[middle] > targht) {
            right = middle;
        }
        else if(arr[middle] < targht) {
            left = middle + 1;
        }
        else if (arr[middle ] == targht) {
            cout << middle  << endl;
            break;
        } else {

        }
    }

    return 0;
}

2.删除数组元素

27. 移除元素 - 力扣（LeetCode）

2.1 快慢指针

  1. 定义一个快指针 int fast = 0，慢指针 int slow = 0；
  2. 用 fast 进行for循环，如果 fast 不等于val，就让arr[slow]等于arr[fast],
    然后slow++；如果等于val，就让fast继续往下跳，直到不等于val，再让arr[slow] = arr[fast]，之后slow++；
  3. 循环结束，返回slow，这时slow等于覆盖完（相当于删除指定元素后）的数组长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0,fast = 0;
        int len = (int)nums.size();
        for(fast = 0; fast < len;++fast) {
            if(nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

2.2 暴力求解

就直接覆盖元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
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;
    }
};

// 时间复杂度：O(n^2)