704.二分查找
·這是三個數的故事
left,middle,right
題目鏈接：https://leetcode.cn/problems/binary-search/
前提：陣列有序??小->大
???陣列無重復數
???使用語言：c++
尋找目標：target
思考路線：l--m--r
?????m找target
?????大小決定m
?????向左or向右
方法一：左閉右閉式 [l,r]
????時間復雜度O(log(n));
????空間復雜度O(1);
class Solution {
public:
int search(vector<int>& nums, int target) {
int m;
int l=0;
int r=nums.size()-1;
while(l<=r){
m=(l+r)/2;
if(target<nums[m]){
r=m-1;//注意！
}
else if(target>nums[m]){
l=m+1;//注意！
}
else if(target==nums[m]){
return m;
}
}
return -1;
}
};
困難筆記：
??r=m和l=m造成了跳不出回圈的問題
??原因：重復計算，陷入死回圈
??理解：左閉右閉的形式下，左右邊界值必定不包含前一次回圈的中間值，因為前一次回圈的中間值已經被判斷過了，
方法二：左閉右開式 [l,r)
????時間復雜度O(log(n));
????空間復雜度O(1);
class Solution {
public:
int search(vector<int>& nums, int target) {
int m;
int l=0;
int r=nums.size();//區別
while(l<r){//因為[l,r)中l與r不能相等
m=(l+r)/2;
if(target<nums[m]){
r=m;//區別
}
else if(target>nums[m]){
l=m+1;//區別
}
else if(target==nums[m]){
return m;
}
}
return -1;
}
};
區別筆記：這里的r應該是右邊的數+1位
識訓摘要：此題需要區分好查找時判斷的邊界問題，注意當次回圈和下一次回圈中三個數的聯系，
越界問題：m=(l+r)/2
?????int相加可能造成越界，
?????可以用如下公式：
?????m=l+(r-l)/2;
學習的文章鏈接：
https://programmercarl.com/0704.二分查找.html
學習的視頻鏈接：
https://www.bilibili.com/video/BV1fA4y1o715
27、移除元素
·無序好耶！doge
不容于nums陣列的val
題目鏈接：https://leetcode.cn/problems/remove-element/
前提：O（1）額外空間
???元素順序可以改變
???不需要考慮超出新長度的陣列元素
想要知道：沒有val陣列有多長？
思考路線：是val就往后靠，讓后邊的上來
方法一：看到題目的第一想法，AC
????時間復雜度O(n);
????空間復雜度O(1);
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int l=nums.size();
int i=0;
while(i<l){
if(nums[i]==val){
nums[i]=nums[l-1];
l--;
}
else{
i++;
}
}
return i;
}
};
思考筆記：應該也是暴力解法（本人最擅長暴力解doge），鑒于本題條件中輸出陣列是無序的，所以沒有進行方法二中的覆寫操作，
方法二：暴力演算法
????時間復雜度O(n^2);
????空間復雜度O(1);
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int l=nums.size();
int i=0;
int j;
for(i=0,i<l;i++){
if(nums[i]==val){
for(j=i+1;j<l;j++){//進行覆寫
nums[j-1]=nums[j];
}
i--;//下一個陣列元素也可能是val
l--;//陣列長度-1
}
}
return l;
}
};
方法三：雙指標法
????時間復雜度O(n);
????空間復雜度O(1);
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int l=nums.size();
int i=0;
int slow=0;
for(int fast=0;fast<l;fast++){
if(nums[fast]!=val){//快指標指向的不是val就可以對慢指標指向的陣列元素進行覆寫
nums[slow]=nums[fast];
slow++;
}
}
return slow;
}
};
感悟筆記：雙指標好快！
摘要筆記：雙指標妙啊~~
學習的文章鏈接：
https://programmercarl.com/0027.移除元素.html
學習的視頻鏈接：
https://www.bilibili.com/video/BV12A4y1Z7LP
今日學習時長：4h30min
Day01：好的開始，繼續努力！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/520662.html
標籤：其他