數(shù)組

數(shù)組是存放在連續(xù)內存空間上的相同類型數(shù)據(jù)的集合。

創(chuàng)新互聯(lián)公司長期為上千多家客戶提供的網(wǎng)站建設服務，團隊從業(yè)經(jīng)驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為牡丹企業(yè)提供專業(yè)的網(wǎng)站設計、成都做網(wǎng)站，牡丹網(wǎng)站改版等技術服務。擁有十年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

①數(shù)組的下標都是從0開始的
②數(shù)組內存空間的地址是連續(xù)的

因為數(shù)組在內存空間的地址是連續(xù)的，所以我們在刪除或增添元素的時候，就需要移動其他元素的地址。
注：①vector是容器，array是數(shù)組，vector的底層實現(xiàn)是array。
②數(shù)組的元素是不能刪除的，只能覆蓋。

二維數(shù)組

二維數(shù)組地址測試

#includeusing namespace std;  
  
void Array2DAddress(){int array[2][3] = {{0, 1, 2},{3, 4, 5}};  
    cout<< &array[0][0]<< " "<< &array[0][1]<< " "<< &array[0][2]<< endl;  
    cout<< &array[1][0]<< " "<< &array[1][1]<< " "<< &array[1][2]<< endl;  
}  
int main() {Array2DAddress();  
    return 0;  
}

輸出：

0x16d537760 0x16d537764 0x16d537768
0x16d53776c 0x16d537770 0x16d537774

注：int長度為4個字節(jié)，根據(jù)輸出結果可知，二維數(shù)組的數(shù)據(jù)存儲方式仍然是連續(xù)的。

704.二分查找

題目： 給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標值 target ，寫一個函數(shù)搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
鏈接： https://leetcode.cn/problems/binary-search
思路： 二分查找的循環(huán)不變量規(guī)則，在二分查找的過程中，保持不變量，就是在while尋找中每一次邊界的處理都要堅持根據(jù)區(qū)間的定義來操作。
二分法區(qū)間定義： 左閉右閉[left, right]和左閉右開[left, right)

1. 左閉右閉[left, right]寫法
   定義目標值target在一個左閉右閉[left, right]的區(qū)間里：
   ①while(left<= right)要使用<=因為left == right是有意義的；
   ②if(nums[middle] >target)right = middle - 1，因為此時的nums[middle]一定不等于target；
   ③if(nums[middle]< target)left = middle + 1，因為此時的nums[middle]一定不等于target；

class Solution {public:
	int search(vector& nums, int target) {int left = 0;
		int right = nums.size() - 1;
		while(left<= right){	//int middle = (left + right) / 2;
			int middle = left + (right - left) / 2;
			if(nums[middle] >target){		right = middle - 1;
			}
			else if(nums[middle]< target){		left = middle + 1;
			}
			else{		return middle;
			}
		}
		return -1;
	}
};

2. 左閉右開[left, right)寫法
   定義目標值target在一個左閉右開[left, right）的區(qū)間里：
   注：right = nums.size()來保證target在題目給出的區(qū)間內能遍歷到最后一個元素。
   ①while(left< right)要使用<因為left == right是沒有意義的；
   ②if(nums[middle] >target)right = middle，因為此時的nums[middle]有可能等于target；
   ③if(nums[middle]< target)left = middle + 1，因為此時的nums[middle]一定不等于target；

class Solution {public:
	int search(vector& nums, int target) {int left = 0;
		int right = nums.size();
		while(left< right){	//int middle = (left + right) / 2;
			int middle = left + (right - left) / 2;
			if(nums[middle] >target){		right = middle;
			}
			else if(nums[middle]< target){		left = middle + 1;
			}
			else{		return middle;
			}
		}
		return -1;
	}
};

總結： 二分法在使用的過程中最重要的是弄清楚區(qū)間的定義，在循環(huán)中始終堅持根據(jù)查找區(qū)間的定義來做邊界處理。

35.搜索插入位置

題目： 給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值，并返回其索引。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為 O(log n) 的算法。
鏈接： https://leetcode.cn/problems/search-insert-position
思路： 二分查找，若數(shù)組中存在目標值則為普通的二分查找，若數(shù)組中不存在目標值，則插入位置應該在while循環(huán)跳出時left的位置。

class Solution {public:
	int search(vector& nums, int target) {int left = 0;
		int right = nums.size() - 1;
		while(left<= right){	//int middle = (left + right) / 2;
			int middle = left + (right - left) / 2;
			if(nums[middle] >target){		right = middle - 1;
			}
			else if(nums[middle]< target){		left = middle + 1;
			}
			else{		return middle;
			}
		}
		return left;
	}
};

34.在排序數(shù)組中查找元素的第一個和最后一個位置

題目： 給你一個按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個目標值 target。請你找出給定目標值在數(shù)組中的開始位置和結束位置。如果數(shù)組中不存在目標值 target，返回 [-1, -1]。
鏈接： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
思路： 尋找target在數(shù)組的左右邊界，有三種可能的情況：
①target在數(shù)組范圍之外，也就是大于大的小于最小的。例如數(shù)組{3, 4, 5}，target為2或者數(shù)組{3, 4, 5},target為6，此時應該返回[-1,-1]。
②target在數(shù)組范圍之內，但數(shù)組中不存在target。例如數(shù)組{3, 4, 7}，target為5，此時應該返回[-1,-1]。
③target在數(shù)組范圍之內，但數(shù)組中存在target。例如數(shù)組{3, 6, 7}，target為6，此時應該返回[1, 1]。

1. 二分查找，首先兩次二分查找分別找到左邊界leftIdx和右邊界rightIdx，校驗[left, right]是否滿足條件，不滿足則返回[-1,-1]。
2. 二分查找左邊界leftIdx。

int searchLeftIdx(vector& nums, int target) {int left = 0;
   int right = nums.size() - 1;
   int leftIdx = -1;
   while(left<= right){//int middle = (left + right) / 2;
   	int middle = left + (right - left) / 2;
   	if(nums[middle]<= target){right = middle - 1;
   		leftIdx = right;
   	}
   	else{left = middle + 1;
   	}
   }
   return leftIdx;
}

3. 二分查找右邊界rightIdx。
   注：此右邊界rightIdx是第一個大于target的元素的位置。

int searchRightIdx(vector& nums, int target) {int left = 0;
  int right = nums.size() - 1;
  int rightIdx = -1;
  while(left<= right){//int middle = (left + right) / 2;
  	int middle = left + (right - left) / 2;
  	if(nums[middle] >target){right = middle - 1;
  	}
  	else{left = middle + 1;
  		rightIdx = left;
  	}
  }
  return rightIdx;
}

4. 檢驗+約束

vectorsearchRange(vector& nums, int target) {int leftIdx = searchLeftIdx(nums, target) + 1;
	int rightIdx = searchRightIdx(nums, target) - 1;
	if(leftIdx<= rightIdx && nums[leftIdx] == target && nums[rightIdx] == target){return vector{leftIdx, rightIdx};
	}
	return vector{-1, -1};
	}

27.移除元素

題目： 給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
鏈接： https://leetcode.cn/problems/remove-element
注意： 數(shù)組元素在內存地址中是連續(xù)的，不能單獨刪除數(shù)組中的某個元素，只能覆蓋。
思路：

1. 暴力解法
   兩層for循環(huán)，一層for循環(huán)遍歷數(shù)組元素，一層for循環(huán)更新數(shù)組。

class Solution {public:
	int removeElement(vector& 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)
空間復雜度：O(1)
2. 雙指針法
通過一個快指針和慢指針在一層for循環(huán)下完成兩個for循環(huán)的工作。
快指針：尋找新數(shù)組的元素，新數(shù)組就是不包含目標元素的數(shù)組
慢指針：指向更新新數(shù)組下標的位置。

class Solution {public:
	int removeElement(vector& nums, int val) {int slowPointer = 0;
		for(int fastPointer = 0; fastPointer< nums.size(); ++fastPointer){	if(nums[fastPointer] != val){		nums[slowPointer] = nums[fastPointer];
				slowPointer++;
			}
		}
		return slowPointer;
	}
};

時間復雜度：O(N)
空間復雜度：O(1)

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標題：代碼隨想錄算法訓練營第1天|數(shù)組1-創(chuàng)新互聯(lián)
當前URL：http://www.chinadenli.net/article24/dcdjje.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設計、微信公眾號、虛擬主機、面包屑導航、做網(wǎng)站、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)