day 1 第一章 數(shù)組
今日任務(wù)
數(shù)組理論基礎(chǔ)，704. 二分查找喘漏，27. 移除元素
數(shù)組基礎(chǔ)理論
- 數(shù)組下標都是從0開始的
- 數(shù)組內(nèi)存空間的地址是連續(xù)的护蝶。 所以在刪除或者增添元素的時候，要移動其他元素的地址
數(shù)組的元素是不能刪的翩迈，只能覆蓋持灰。
704. 二分查找
給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標值 target ，寫一個函數(shù)搜索 nums 中的 target负饲，如果目標值存在返回下標堤魁，否則返回 -1。
思路：
找到中間值mid返十，
如果target < nums[mid], 說明target應(yīng)該mid左邊妥泉，新的搜索范圍應(yīng)為[left, mid -1];
反之，如果target > nums[mid],說明目標target在mid右邊洞坑，下次搜索范圍應(yīng)為[mid + 1, right];
注意循環(huán)邊界：定義 target 是在一個在左閉右閉的區(qū)間里盲链，也就是[left, right]
code:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while(left <= right){ //左閉右閉
mid = (left + right) / 2; //有int溢出風險，可以改進
if(target == nums[mid]) return mid;
if(target < nums[mid]){
right = mid - 1;
}
else if(target > nums[mid]){
left = mid + 1;
}
}
return -1;
}
}
這里 mid = (left + right) / 2; 有int溢出風險，可以改進刽沾。
而且因為當前數(shù)組為升序數(shù)組本慕，當target < nums[0] or target > nums[nums.length - 1]時，可以直接返回-1悠轩。
如下：
class Solution {
public int search(int[] nums, int target) {
// 避免當 target 小于nums[0] nums[nums.length - 1]時多次循環(huán)運算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
//或 mid = left + (right - left)/2, 避免int溢出風險
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
}
時間復雜度 O(logn)
27. 移除元素
給你一個數(shù)組 nums 和一個值 val间狂，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度火架。
不要使用額外的數(shù)組空間鉴象，你必須僅使用 O(1) 額外空間并原地修改輸入數(shù)組。
元素的順序可以改變何鸡。你不需要考慮數(shù)組中超出新長度后面的元素纺弊。
方法一 ： 左右指針
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0, right = nums.length - 1;
while(right > 0 && nums[right] == val) right--;
while(left <= right){
if(nums[left] == val){
nums[left] = nums[right]; //將right位置的元素移到left(覆蓋),right位置移除
right--;
continue;
}
if(right > 0 && nums[right] == val) right--;
left++;
}
return left;
}
}
方法二 : 快慢指針
雙指針法（快慢指針法）：通過一個快指針和慢指針在一個for循環(huán)下完成兩個for循環(huán)的工作。
快指針用來從頭到尾依次遍歷這個原數(shù)組骡男，然后用當遍歷到不是val的數(shù)時淆游，這個數(shù)組對應(yīng)的慢指針指向的索引的數(shù)更新，慢指針加一隔盛。
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
for(int right = 0; right < nums.length; right++){
if(nums[right] != val){
nums[left] = nums[right];
left++;
}
}
return left;
}
}
以上兩種方法時間復雜度為O(n); 空間復雜度為O(1)
