代码随想录——数组

代码随想录——数组

目录

1. 数组

1.1 二分查找（二分法!!!!）

1.2 移除元素（双指针）

1.3 有序数组的平方（双指针）

1.4 长度最小的子数组 （滑动窗口）

1.5 螺旋矩阵II 

1. 数组

• 数组是存放在连续内存空间上的相同类型数据的集合。
• 数组下标都是从0开始的。
• 数组内存空间的地址是连续的。
• 数组的元素是不能删的，只能覆盖。

注意：vector 和 array的区别。vector是顺序容器，vector的底层实现是array，其利用连续的内存空间来存储元素，但是其内存空间大小是能够改变的；array是顺序容器，其也是利用连续的内存空间来存储元素，但它的内存空间是固定大小的，申请之后就无法改变。

1.1 二分查找（二分法）

704. 二分查找

循环不变量原则，只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。

左闭右闭：while(left <= right),当left=right时有意义；right=middle+1，left=middle-1，

左闭右开：while(left < right),当left=right时没有意义；right=middle，left=middle-1，

// 版本一[left, right]
//暴力解法时间复杂度：O(n)
//二分法时间复杂度：O(logn)
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;//如果题目要求返回插入点return right + 1;}
};// 版本二[left, right)
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <int middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle; // target 在左区间，在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，在[middle + 1, right)中} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;//如果题目要求返回插入点return right;}
};//暴力解法
class Solution {
public:int searchInsert(vector<int>& nums, int target) {for (int i = 0; i < nums.size(); i++) {if (nums[i] >= target) { // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果return i;}}// 目标值在数组所有元素之后的情况return -1;}
};//递归法

35. 搜索插入位置 - 力扣（LeetCode）

（多了返回插入点这一要求）

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）（难点在于找左右边界）

//两个二分法（左闭右闭）
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一if (leftBorder == -2 || rightBorder == -2) return {-1, -1};// 情况三if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getRightBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
};//一个二分法

69. x 的平方根 

class Solution {
public:int mySqrt(int x) {int ans = -1;int left =0, right = x;while (left <= right) {int mid = left + (right - left) / 2;if ((long long) mid * mid <= x) {left = mid + 1;ans = mid;}else {right = mid - 1;}}return ans;}
};

367. 有效的完全平方数

class Solution {
public:bool isPerfectSquare(int num) {int ans  = -1, left = 0, right = num;while (left <= right) {int mid = left + (right - left) / 2;if ((long)mid * mid < num) {left = mid + 1;}if ((long)mid * mid > num) {right = mid - 1;}if ((long)mid * mid == num) {return ans  = mid;}}return ans == -1 ? false : true;}
};

1.2 移除元素（双指针）

27. 移除元素

//暴力解法
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
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--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};

//双指针法（快慢指针法）
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex]; //先赋值在移动满指针}}return slowIndex;}
};

/**
* 相向双指针方法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
class Solution {
public:int removeElement(vector<int>& nums, int val) {int leftIndex = 0;int rightIndex = nums.size() - 1;while (leftIndex <= rightIndex) {// 找左边等于val的元素while (leftIndex <= rightIndex && nums[leftIndex] != val){++leftIndex;}// 找右边不等于val的元素while (leftIndex <= rightIndex && nums[rightIndex] == val) {-- rightIndex;}// 将右边不等于val的元素覆盖左边等于val的元素if (leftIndex < rightIndex) {nums[leftIndex++] = nums[rightIndex--];}}return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素}
};

没看懂第三个方法相向双指针？？ 

1.3 有序数组的平方（双指针）

977. 有序数组的平方

快排函数sort

//暴力解法
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i = 0; i<nums.size() ; i++){nums[i]*=nums[i];}sort(nums.begin(), d());return nums;}
};

//双指针法
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int k = nums.size() - 1;vector<int> result(nums.size(), 0); //result来存放新的排序后的数组for (int i = 0, j = nums.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素if (nums[i] * nums[i] < nums[j] * nums[j])  {result[k--] = nums[j] * nums[j];j--;}else {result[k--] = nums[i] * nums[i];i++;}}return result;}
};

1.4 长度最小的子数组 （滑动窗口）

209. 长度最小的子数组

//暴力解法
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX; // 最终的结果//INT_MAX是个很大的数，如果想得到数组中最小值，可以先将minn设成INX_MAX,这样就不需要const int定义一个很大的数了，还有很多地方都可以使用它int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为isum = 0;for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为jsum += nums[j];if (sum >= s) { // 一旦发现子序列和超过了s，更新resultsubLength = j - i + 1; // 取子序列的长度result = result < subLength ? result : subLength;// 如果?前面的式子为真，那么就返回冒号：左边的值；否则返回右边的值。break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break}}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};

//滑动窗口法
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX;int sum = 0; // 滑动窗口数值之和int i = 0; // 滑动窗口起始位置int subLength = 0; // 滑动窗口的长度for (int j = 0; j < nums.size(); j++) {sum += nums[j];// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件while (sum >= s) {subLength = (j - i + 1); // 取子序列的长度result = result < subLength ? result : subLength;sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};

1.5 螺旋矩阵II 

59. 螺旋矩阵 II

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组int startx = 0, starty = 0; // 定义每循环一个圈的起始位置int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)int count = 1; // 用来给矩阵中每一个空格赋值int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位int i,j;while (loop --) {i = startx;j = starty;// 下面开始的四个for就是模拟转了一圈// 模拟填充上行从左到右(左闭右开)for (j = starty; j < n - offset; j++) {res[startx][j] = count++;}// 模拟填充右列从上到下(左闭右开)for (i = startx; i < n - offset; i++) {res[i][j] = count++;}// 模拟填充下行从右到左(左闭右开)for (; j > starty; j--) {res[i][j] = count++;}// 模拟填充左列从下到上(左闭右开)for (; i > startx; i--) {res[i][j] = count++;}// 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)startx++;starty++;// offset 控制每一圈里每一条边遍历的长度offset += 1;}// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值if (n % 2) {res[mid][mid] = count;}return res;}
};