数据结构----结构--线性结构--顺序存储--数组
数据结构----结构–线性结构–顺序存储–数组
数组：类型相同，空间连续，长度固定
搜索：
（1）基于索引搜索，时间复杂度O(1)
（2）基于数值搜索：
1.有序的：二分查找
2.无需的：遍历一遍O(n)
增删：
空间不够：扩容 旧数据->新数据 迁移
空间足够：尾增尾删O(1) 其他增删O(n)
关于数组特性的题
第一题
题目：给一个有n个元素的数组，数组内的元素数值范围在0~n-1之间。请检测：数据有无重复出现，如果出现请报错
解决方法：1.暴力 时间复杂度O(n的平方) 空间复杂度 O(1)
2.计数 时间复杂度O(n) 空间复杂度 O(n)
3.排序: 时间复杂度O(看利用哪种排序) 空间复杂度 O(看利用哪种排序)
4.set/map 时间复杂度O(nlog2的n次方) 空间复杂度O(nlog2的n次方)
5.交换 时间复杂度O(n) 空间复杂度 O(1)
这里交换的方法最好 我们用代码实现一下
#include<iostream>
using namespace std;//判断的函数
void PanDuan(int a[],int length) {for (int i = 0; i < length;) {//遍历if (a[i] == i) {//如果下标和数对上了就下一个i++;}else {if (a[i] == a[a[i]]) {//重复cout << "错误" << endl;break;}else {//不重复交换位置int t;t = a[i];a[i] = a[a[i]];a[t] = t;}}
}
int main() {int a[] = { 0,3,2,4,1 };//定义一个数组，进行测试PanDuan(a,(sizeof(a)/sizeof(a[0])));//进入判断的函数return 0;
}
第二题
题目：一组数据，其中有一个元素只出现一次，其他元素均出现两次，请找出只出现一次的元素
解决方法：1.暴力 时间复杂度O(n的平方) 空间复杂度 O(1)
2.计数 (哈希表，map)
哈希表 时间复杂度O(n) 空间复杂度 O(n)
map 时间复杂度O(nlog2的n次方) 空间复杂度 O(n)
3.异或 时间复杂度O(n) 空间复杂度 O(1)
更改题目为：一组数据，其中有两个元素只出现一次，其他元素均出现两次，请找出只出现一次的元素
最优解决方法: 第一步：整体异或
第二步：找到非0位
第三步：根据非0位进行分组，分为两组
第四步：各组异或 就得到了只出现一次的这两个元素
用代码进行实现，如下
#include <iostream>
using namespace std;void Find(int arr[]){int res1 = 0;for (int i : arr) {//全部异或一遍 获得两个只出现一次元素的异或的结果res1 ^= i;}unsigned int res2 = 1;//从右到左找到二进制上第一个为1的while (1) {//与1进行位于if (res1 & res2) {break;}res2 = res2 << 1;}int result1 = 0;int result2 = 0;for (int i : arr) {//遍历分类并对两组数进行异或得到结果if (res2 & i) {result1 ^= i;}else {result2 ^= i;}}cout << result1 << " " << result2 << endl;
}
int main() {int nums[] = { 1,5,5,4,4,3 };//这里是测试样例Find(nums);return 0;
}