type
status
date
slug
summary
tags
category
icon
password
0. 数组操作
1.打印数组
功能：打印数组
ar 中 [start, end) 范围内的元素，以空格分隔，末尾换行。参数：
ar[]：目标数组。
start：起始下标（包含）。
end：结束下标（不包含）。
注：需确保
0 ≤ start ≤ end ≤ 数组长度。2.查找元素
功能：在数组
ar 的 [start, end) 范围内线性查找 key，返回其首次出现的下标，未找到返回 -1。参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
key：待查找值
时间复杂度：O(n)
3.查找最大值
功能：查找数组
ar 在 [start, end) 范围内的最大值。参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
返回值：区间内的最大值
时间复杂度：O(n)
4.查找次大值
功能：查找数组
ar 在 [start, end) 范围内的第二大值参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
返回值：区间内的第二大值
注意：
- 数组长度至少为2，否则行为未定义
- 如果有多个相同的最大值，返回第二大值（即可能等于最大值）
时间复杂度：O(n)
5.排序
功能：对数组
ar 的 [start, end) 范围进行升序冒泡排序参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
特性：
- 原地排序（无需额外空间）
- 稳定排序（相等元素相对位置不变）
时间复杂度：
- 最优：O(n)（已排序时）
- 最差：O(n²)（完全逆序时）
6.逆置
功能：原地反转数组
ar 的 [start, end) 区间元素顺序参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
特性：
- 时间复杂度：O(n/2) → 高效
- 空间复杂度：O(1) → 原地操作
注意：
- 当
start >= end-1时不执行任何操作
7.二分查找
功能：在已排序数组
ar 的 [start, end) 范围内二分查找 key参数：
ar[]：已排序的目标数组（升序）
start：起始下标（包含）
end：结束下标（不包含）
key：待查找值
返回值：
- 找到时返回元素下标
- 未找到返回
-1
时间复杂度：O(log n)
8.找出只出现一次的元素
功能：在数组
ar 的 [start, end) 范围内找出唯一出现奇数次的数字（其他数字必须出现偶数次）参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
返回值：
- 唯一出现奇数次的数字
- 若所有数字出现偶数次，返回
0
原理：
- 利用异或运算性质：
a ^ a = 0a ^ 0 = a- 异或满足交换律和结合律
时间复杂度：O(n)
注意：
- 仅当恰好一个数字出现奇数次时结果正确
- 若多个数字出现奇数次，结果为它们的异或值（非预期）
- 默认初始值
res=0，因此无奇数次数时返回0
9.找出出现一次的两个元素
功能：在数组
ar 的 [start, end) 范围内找出两个各出现奇数次的数字（其他数字必须出现偶数次）参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
返回值：
- 静态数组指针
ret，包含两个结果数字： ret[0]：第一个奇数次数ret[1]：第二个奇数次数
原理：
- 第一次异或得到
_xor = num1 ^ num2
- 通过
mask找到num1和num2的不同比特位
- 分组异或分离出两个数
时间复杂度：O(n)
注意：
- 必须保证其他数字都出现偶数次，否则结果不可靠
- 使用静态数组存储结果，多次调用会覆盖之前的结果
- 若数组不符合条件（如所有数字出现偶数次），返回值无意义
10.头部插入一个元素
功能：在数组
ar 的 [start, end) 范围内头部插入元素，并右移其他元素参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
value：待插入的值
返回值：
true：插入成功
- 注意：若数组已满（无空间右移），会丢失
ar[end-1]的值
时间复杂度：O(n)
关键点：
- 需要确保数组容量足够（
end不超过数组实际长度）
- 原
ar[start]~ar[end-2]的元素会被向后移动一位
- 会覆盖
ar[end-1]的值（设计需注意）
11.删除元素
功能：在数组
ar 的 [start, end) 范围内删除第一个等于 key 的元素，后续元素左移填补空缺参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
key：待删除的值
返回值：
true：删除成功
false：未找到key
时间复杂度：O(n)（查找+移动）
注意：
- 会修改原数组长度逻辑（调用方需自行维护有效长度）
- 实际数组容量需足够（避免越界）
- 仅删除第一个匹配项
12.旋转数组
功能：将数组
ar 的 [start, end) 区间循环右移 k 位参数：
ar[]：目标数组
start：起始下标（包含）
end：结束下标（不包含）
k：右移位数（自动取模处理大数）、
时间复杂度：O(n)（三次反转）
- Author:Blinky
- URL:http://preview.tangly1024.com/article/cprogrammingarray
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
