代码随想录算法训练营第1天|数组1-创新互联

数组

数组是存放在连续内存空间上的相同类型数据的集合。

创新互联公司长期为上千多家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为牡丹企业提供专业的网站设计、成都做网站，牡丹网站改版等技术服务。拥有十年丰富建站经验和众多成功案例,为您定制开发。

①数组的下标都是从0开始的
②数组内存空间的地址是连续的

因为数组在内存空间的地址是连续的，所以我们在删除或增添元素的时候，就需要移动其他元素的地址。
注：①vector是容器，array是数组，vector的底层实现是array。
②数组的元素是不能删除的，只能覆盖。

二维数组

二维数组地址测试

#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个字节，根据输出结果可知，二维数组的数据存储方式仍然是连续的。

704.二分查找

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
链接： https://leetcode.cn/problems/binary-search
思路：二分查找的循环不变量规则，在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作。
二分法区间定义：左闭右闭[left, right]和左闭右开[left, right)

左闭右闭[left, right]写法
定义目标值target在一个左闭右闭[left, right]的区间里：
①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;
	}
};

左闭右开[left, right)写法
定义目标值target在一个左闭右开[left, right）的区间里：
注：right = nums.size()来保证target在题目给出的区间内能遍历到最后一个元素。
①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;
	}
};

总结：二分法在使用的过程中最重要的是弄清楚区间的定义，在循环中始终坚持根据查找区间的定义来做边界处理。

35.搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
链接： https://leetcode.cn/problems/search-insert-position
思路：二分查找，若数组中存在目标值则为普通的二分查找，若数组中不存在目标值，则插入位置应该在while循环跳出时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.在排序数组中查找元素的第一个和最后一个位置

题目：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
链接： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
思路：寻找target在数组的左右边界，有三种可能的情况：
①target在数组范围之外，也就是大于大的小于最小的。例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回[-1,-1]。
②target在数组范围之内，但数组中不存在target。例如数组{3, 4, 7}，target为5，此时应该返回[-1,-1]。
③target在数组范围之内，但数组中存在target。例如数组{3, 6, 7}，target为6，此时应该返回[1, 1]。

二分查找，首先两次二分查找分别找到左边界leftIdx和右边界rightIdx，校验[left, right]是否满足条件，不满足则返回[-1,-1]。
二分查找左边界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;
}

二分查找右边界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;
}

检验+约束

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.移除元素

题目：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
链接： https://leetcode.cn/problems/remove-element
注意：数组元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
思路：

暴力解法
两层for循环，一层for循环遍历数组元素，一层for循环更新数组。

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循环下完成两个for循环的工作。
快指针：寻找新数组的元素，新数组就是不包含目标元素的数组
慢指针：指向更新新数组下标的位置。

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)

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页题目：代码随想录算法训练营第1天|数组1-创新互联
标题URL：http://myzitong.com/article/dcdjje.html

代码随想录算法训练营第1天|数组1-创新互联

其他资讯