电商商城网站,合肥建设管理学校网站首页,重庆渝网站建设,wordpress替换链接数据结构----结构–线性结构–顺序存储–数组
数组#xff1a;类型相同#xff0c;空间连续#xff0c;长度固定
搜索#xff1a;
#xff08;1#xff09;基于索引搜索#xff0c;时间复杂度O(1)
#xff08;2#xff09;基于数值搜索#xff1a;
1.有序的类型相同空间连续长度固定
搜索
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)
这里交换的方法最好 我们用代码实现一下
#includeiostream
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;
}
