线性时间复杂度简介
线性时间复杂度，通常表示为 O(n)，意味着算法的执行时间与输入数据的大小成正比。这种复杂度级别的算法在处理大数据集时表现出色，因为它们能够以相对较小的时间成本完成任务。
寻找数组中的最大值
寻找数组中的最大值是一个常见的问题，可以使用简单的线性扫描来解决。
算法描述
遍历数组，通过比较每个元素来找到最大的那个。
示例代码
// www.javascriptcn.com code example
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 测试代码
console.log(findMax([3, 5, 1, 2, 4])); // 输出：5复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。
- 空间复杂度：O(1)，仅使用了常数级额外空间。
计算数组元素之和
计算数组中所有元素的和是另一个典型的线性时间复杂度问题。
算法描述
遍历数组并将所有元素相加得到总和。
示例代码
// www.javascriptcn.com code example
function sumArray(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
// 测试代码
console.log(sumArray([1, 2, 3, 4, 5])); // 输出：15复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。
- 空间复杂度：O(1)，仅使用了常数级额外空间。
判断数组是否包含重复元素
检查一个数组中是否存在重复元素的问题可以通过哈希表来高效解决。
算法描述
遍历数组，使用一个哈希表记录已经遇到过的元素。如果某个元素已经在哈希表中出现，则说明存在重复元素。
示例代码
// www.javascriptcn.com code example
function hasDuplicate(arr) {
const seen = new Set();
for (let i = 0; i < arr.length; i++) {
if (seen.has(arr[i])) {
return true;
}
seen.add(arr[i]);
}
return false;
}
// 测试代码
console.log(hasDuplicate([1, 2, 3, 4, 5])); // 输出：false
console.log(hasDuplicate([1, 2, 3, 4, 5, 2])); // 输出：true复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。
- 空间复杂度：O(n)，最坏情况下，所有的元素都不相同，需要存储 n 个元素。
检查两个字符串是否为异位词
异位词是指两个字符串包含相同的字符但顺序不同。这类问题可以通过计数来解决。
算法描述
遍历第一个字符串并统计每个字符出现的次数，然后遍历第二个字符串减少对应的计数。如果最后所有的计数都为零，则说明这两个字符串是异位词。
示例代码
// www.javascriptcn.com code example
function areAnagrams(str1, str2) {
if (str1.length !== str2.length) {
return false;
}
const charCount = {};
for (let i = 0; i < str1.length; i++) {
const char = str1[i];
charCount[char] = (charCount[char] || 0) + 1;
}
for (let i = 0; i < str2.length; i++) {
const char = str2[i];
if (!charCount[char]) {
return false;
}
charCount[char]--;
}
return true;
}
// 测试代码
console.log(areAnagrams("listen", "silent")); // 输出：true
console.log(areAnagrams("hello", "world")); // 输出：false复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度。
- 空间复杂度：O(1)，字母表大小固定，所以哈希表的大小也是固定的。
查找数组中的两个数使其和为目标值
查找数组中两个数使其和等于目标值是一个常见问题，可以使用哈希表来优化查找过程。
算法描述
遍历数组，使用哈希表记录每个元素的值及其索引位置。对于当前元素，检查目标值减去该元素的结果是否存在于哈希表中，如果存在则找到了一对满足条件的数。
示例代码
// www.javascriptcn.com code example
function twoSum(nums, target) {
const numToIndex = {};
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (complement in numToIndex) {
return [numToIndex[complement], i];
}
numToIndex[nums[i]] = i;
}
return null;
}
// 测试代码
console.log(twoSum([2, 7, 11, 15], 9)); // 输出：[0, 1]复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。
- 空间复杂度：O(n)，最坏情况下，所有的元素都需要存储在哈希表中。