数据结构----结构--线性结构--顺序存储--数组

数据结构----结构–线性结构–顺序存储–数组

数组：类型相同，空间连续，长度固定

搜索：

（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;
}