跳转至

二分查找 & 移除元素 & 有序数组的平方

约 487 个字 135 行代码 预计阅读时间 3 分钟

Luck

荣幸在B站24.01-24抽奖中了Carl哥的算法训练营！(😆) → 参考网站

陆陆续续学过一些算法，争取坚持系统学一遍！

24.12.25-B站抽奖那么幸运又中了

上次打卡到DP太难，遂放弃，作为算法菜鸟希望这次尽可能坚持！

PS: 准备这次用Java，虽然主要是算法思想并没太大的区别

  • 但因为也快秋招了，为了最后起码能保底拿个offer，思来想去还是Java可能更合适一些

（即便很想研究C++，但感觉时间很不够了，论文还没弄出来而且C++基础并没很好，最重要的C++就业门槛更高一些，而Java开发选择面更广一些，甚至银行等国企可能还有机会）

704.二分查找

第一想法：暴力求呗，因为是升序的，直接循环找即可 

1
2
3
4
5
6
7
class Solution {
    public int search(int[] nums, int target) {
        for(int i = 0; i < nums.length; i ++)
            if(nums[i] == target) return i;
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    } 
};

但题目是 二分查找 呀！而且数组有序，定考虑二分 (区间要注意!)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > target) r = mid - 1;
            else if(nums[mid] < target) l = mid + 1;
            else return mid;
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1; // index 

        while(l <= r) {
            int mid = l + ((r - l) >> 1); // 防溢出
            if (nums[mid] > target) r = mid - 1;
            else if (nums[mid] < target) l = mid + 1;
            else return mid;
        }
        return -1;
    }
};

27.移除元素

原地移除等于val的元素 & 空间要求\(O(1)\)，最终返回新的数组长度

原地如何移除？数组元素能删除？ → NO，本质即 覆盖 呗!

  1. 想法: 暴力 → 循环找到目标val，循环后一个先前进行覆盖
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        for (int i = 0; i < n; i ++) {
            if(nums[i] == val) {
                for(int j = i + 1; j < n; j ++) nums[j - 1] = nums[j];
                i --;
                n --;
            }
        }
        return n;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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; 
    }
};
  1. 快慢指针 → ref, 动图参考
    • 对暴力进行优化，利用双指针降低复杂度（即一层循环\(O(n)\)

快指针来索引新数组需要的元素，更新到慢指针索引上，最终返回慢指针即可（太强了!!!

1
2
3
4
5
6
7
8
class Solution {
    public int removeElement(int[] nums, int val) {
        int s = 0;
        for (int f = 0; f < nums.length; f ++)
            if (nums[f] != val) nums[s ++] = nums[f];
        return s;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
    }
};

977.有序数组的平方

第一想法: 对每个数进行平方，然后排序即可

1
2
3
4
5
6
7
8
class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0; i < nums.length; i ++)  
            nums[i] = nums[i] * nums[i];
        Arrays.sort(nums); // 对array排序
        return nums;
    }
}

1
2
3
4
5
6
7
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;
}

时间复杂度: \(O(n + nlogn)\)

2.双指针 → 因为有序，最大值必在两端，两边扫描比较，开个数组，空间换时间(动图)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int i = 0, j = nums.length - 1, k = nums.length - 1;
        while(i <= j) {
            if(nums[i] * nums[i] < nums[j] * nums[j]) {
                res[k --] = nums[j] * nums[j];
                j --;
            }
            else {
                res[k --] = nums[i] * nums[i];
                i ++;
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
vector<int> sortedSquares(vector<int>& nums) {
    vector<int> vec = nums;
    int i = 0, j = nums.size() - 1, k = nums.size() - 1;
    while (i <= j) {
        if (nums[i] * nums[i] < nums[j] * nums[j]) {
            vec[k --] = nums[j] * nums[j];
            j --;
        } else {
            vec[k --] = nums[i] * nums[i];
            i ++;
        }
    }
    return vec;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论