1、概念
数组是存放在连续空间上的相同类型的数据集合。
特点：
1、数组下标都是从0开始的；
2、数组内存空间的地址是连续的。
C++,要注意vector和array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。
C++中二位数组在地址空间是连续的。测试代码：
void test_arr() {
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() {
test_arr();
}
2、二分查找 主要理解区间定义，对循环条件的影响
特点：前提是有序数组，而且没有无重复元素
题目：https://leetcode-cn.com/problems/binary-search/.
首位置 末尾位置，中间位置。
当中间位置的数字>目标数字 末尾位置挪移到中间位置
当中间位置的数字<目标数字 首位置挪移到中间位置
中间位置<0 中间位置>末尾位置 非法边界。
第一种写法 [left,right]
第二种写法[left,right)
int search(int* nums, int numsSize, int target){
int left = 0;
int right = numsSize - 1;
while (left <= right){
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.1搜索插入位置（有序数组，要直接想到二分查找）
/*
题目：https://leetcode.cn/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值
不存在于数组中，返回它将会被按顺序插入的位置。
特点：有序数组
解题思路：
1、用二分查找，查询是否在数组中
2、若在返回索引
3、若不在，移动数组元素，把target插入数组中。从哪个索引开始移动数组元素，target插入
索引位置是哪？
*/
#include <stdio.h>
#define SIZE 4
int searchInsert(int* nums, int numsSize, int target);
int main()
{
int nums[SIZE] = {1,3,5,6};
int target = 0,targetIndex = 0;
printf("请输入你要查询的数值：");
scanf("%d", &target);
targetIndex = searchInsert(nums,SIZE,target);
if (targetIndex != -1)
{
printf("%d的索引是%d\n",target, targetIndex);
}
else
{
for (int i = 0; i < SIZE; i++)
{
printf("%d ",nums[i]);
}
}
}
int searchInsert(int* nums, int numsSize, int target)
{
int left = 0,right = numsSize - 1; //闭区间
int middle = 0;
while (left <= right) //循环条件是<开区间还是<= 为什么？<= 因为选择的闭区间的写法。若是选择左闭右开的写法 选择<,并且保证循环过程中区间都是左闭右开。
{
middle = left + ((right - left) << 2); //防止索引越界
if (target < nums[middle])
{
right = middle -1; //保持循环过程中是闭区间
}
else if (target > nums[middle])
{
left = middle + 1; //保持循环过程中是闭区间
}
else
{
return middle;
}
}
return left; //为什么是left而不是middle。循环结束时，left的值满足。
}
2.2 在排序数组中查找元素的第一个和最后一个位置
题目：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
解题思路：
2.3 x 的平方根
题目：https://leetcode.cn/problems/sqrtx/
解题思路：
2.4 有效的完全平方数
题目：https://leetcode.cn/problems/valid-perfect-square/
解题思路：
3、移除元素
题目：https://leetcode-cn.com/problems/remove-element/
第一种：暴力实现
第二种：双指针：一个快指针，一个慢指针
快指针是寻找这个新数组里所需要的元素（除去所需要删除目标元素的元素）
新数组的更新的位置就是slow。
在快指针获取到的值赋给慢指针就可以了。
int removeElement(int* nums, int numsSize, int val){
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < numsSize; fastIndex++){
if (val != nums[fastIndex]){
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
};
类似题目：
26 删除排序数组中的重复项
283 移动零
844 比较含退格的字符串
有序数组的平方
题目：https://leetcode-cn.com/problems/squares-of-a-sorted-array/
第一种方法：暴力解法 每个数平方之后，排序即可
第二种方法：双指针法
考虑题目的特征：有序数组，那么数组的平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法，i指向起始位置，j指向终止位置
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
怎么想到定义了一个新数组？因为数组的元素已经改变，不仅是位置的改变还有内容的改变。文章来源：https://www.toymoban.com/news/detail-421304.html
#include <stdio.h>
#include <math.h>
int main()
{
int originalArr[5] = {-3,-2,4,5,6};
int newArr[5] = {0};
int i = 0;
int j = 4;
int k = 4;
/*
首先比较初始元素的平方和末尾元素的平方大小
其次，将较大的一方放入新数组的末尾位置，并移动i或j的位置。
循环结束的条件，i <= j
*/
while (i <= j)
{
if (pow(originalArr[i],2) > pow(originalArr[j],2))
{
newArr[k] = pow(originalArr[i],2);
i++;
k--;
}
else
{
newArr[k] = pow(originalArr[j],2);
j--;
k--;
}
}
for (int i = 0; i < 5; i++)
{
printf("%d ",newArr[i]);
}
return 0;
}
长度最小的子数组（滑动窗口）
螺旋矩阵
题目：https://leetcode-cn.com/problems/spiral-matrix-ii/文章来源地址https://www.toymoban.com/news/detail-421304.html
总结
到了这里，关于数组的知识点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
