公司品牌官网建站/站长统计

嵌入式软件数据结构（二）数组知识点专栏 附源码 附原理  前言：

首先我们要知道什么是数组？

数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力。也就是说，想法很简单，但实现起来 可能就不是那么回事了。首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题

数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便的通过下标索引的方式获取到下标对应的数据。

数组的内存是连续的，元素在内存中依次存放。例如，一个包含5个整数的数组，在内存中会占用5个连续的内存地址。每个数组元素的大小由其类型决定（如int通常占4字节，char占1字节等）。

int arr[5] = {1, 2, 3, 4, 5};

在内存中，它的存储方式可能像这样：

地址	1st Element	2nd Element	3rd Element	4th Element	5th Element
0x0010	1	2	3	4	5

arr[0]存储在地址0x0010，arr[1]存储在0x0014，以此类推（假设int类型占4字节）。

需要两点注意的是

数组下标都是从0开始的。

数组内存空间的地址是连续的

正是因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：

而且大家如果使用C++的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。

数组的元素是不能删的，只能覆盖。

那么二维数组在内存的空间地址是连续的么？不同编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的。

最大子序和

53. 最大子数组和 - 力扣（LeetCode）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

子数组 是数组中连续的 非空 元素序列。

int maxSubArray(int* nums, int numsSize) {int maxsum = nums[0];int cursum = nums[0];for(int i = 1 ; i < numsSize ; ++i){cursum = (cursum > 0) ? (cursum + nums[i]) : nums[i];if(cursum > maxsum){maxsum = cursum;}}return maxsum;
}

移除元素

27. 移除元素 - 力扣（LeetCode）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。// 它以不等于 val 的值排序。int k = removeElement(nums, val); // 调用你的实现assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

int removeElement(int* nums, int numsSize, int val) {int k = 0;for(int i=0 ; i < numsSize ; ++i){if (nums[i] != val) { nums[k] = nums[i]; k++; }}return k; 
}

合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int i = m - 1;       // 指向 nums1 的最后一个有效元素int j = n - 1;       // 指向 nums2 的最后一个元素int k = m + n - 1;   // 指向合并后 nums1 的最后一个位置// 从后往前合并while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];  // 把大的放到后面} else {nums1[k--] = nums2[j--];  // 把 nums2[j] 放到后面}}// 处理 nums2 剩余的元素（如果 nums1 剩余的元素已经在原地，无需额外处理）while (j >= 0) {nums1[k--] = nums2[j--];}
}

查找常用字符

1002. 查找共用字符 - 力扣（LeetCode）

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

/*** Note: The returned array must be malloced, assume caller calls free().*/
char** commonChars(char** words, int wordsSize, int* returnSize) {int minFreq[26]; // 记录所有单词中的最小字符频率memset(minFreq, 127, sizeof(minFreq)); // 初始化为一个较大值 (127, 因为 int 的最大值会影响求 min)// 遍历每个单词，更新 minFreqfor (int i = 0; i < wordsSize; i++) {int freq[26] = {0}; // 当前单词的字符频率for (int j = 0; words[i][j] != '\0'; j++) {freq[words[i][j] - 'a']++;}// 更新 minFreqfor (int k = 0; k < 26; k++) {if (minFreq[k] > freq[k]) {minFreq[k] = freq[k];}}}// 构造返回结果char** result = (char**)malloc(100 * sizeof(char*)); // 假设最多 100 个字符*returnSize = 0;for (int i = 0; i < 26; i++) {while (minFreq[i]-- > 0) {result[*returnSize] = (char*)malloc(2 * sizeof(char));result[*returnSize][0] = 'a' + i;result[*returnSize][1] = '\0';(*returnSize)++;}}return result;
}

寻找数组的中心索引

724. 寻找数组的中心下标 - 力扣（LeetCode）

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

int pivotIndex(int* nums, int numsSize) {int totalSum = 0;   // 数组总和int leftSum = 0;     // 左侧和// 计算数组的总和for (int i = 0; i < numsSize; i++) {totalSum += nums[i];}// 遍历数组，检查每个下标是否满足条件for (int i = 0; i < numsSize; i++) {// 右侧和 = totalSum - leftSum - nums[i]if (leftSum == totalSum - leftSum - nums[i]) {return i;  // 找到中心下标，返回}// 更新左侧和leftSum += nums[i];}return -1;  // 如果没有找到中心下标，返回 -1
}

数组中数字出现的次数

LCR 177. 撞色搭配 - 力扣（LeetCode）

整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sockCollocation(int* sockets, int socketsSize, int* returnSize) {int xorResult = 0;// 第一步：对所有数字进行异或运算for (int i = 0; i < socketsSize; i++) {xorResult ^= sockets[i];}// 第二步：找到一个非零的位（即异或结果中的一个1的位置）int bit = xorResult & -xorResult; // 取最低位的1// 第三步：将数组分为两组并分别异或int* result = (int*)malloc(2 * sizeof(int));int group1 = 0, group2 = 0;for (int i = 0; i < socketsSize; i++) {if (sockets[i] & bit) {group1 ^= sockets[i]; // 位为1的组} else {group2 ^= sockets[i]; // 位为0的组}}// 将结果保存到返回数组中result[0] = group1;result[1] = group2;*returnSize = 2;return result;
}

数组中缺失的元素

268. 丢失的数字 - 力扣（LeetCode）

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

int missingNumber(int* nums, int numsSize) {// 计算预期的总和int sum_expected = numsSize * (numsSize + 1) / 2;// 计算实际的总和int sum_actual = 0;for (int i = 0; i < numsSize; i++) {sum_actual += nums[i];}// 计算缺失的数字return sum_expected - sum_actual;
}

按奇偶排序数组

905. 按奇偶排序数组 - 力扣（LeetCode）

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

int* sortArrayByParity(int* nums, int numsSize, int* returnSize) {int left = 0, right = numsSize - 1;// 使用双指针法处理数组while (left < right) {// 左指针找到奇数，右指针找到偶数时交换if (nums[left] % 2 == 1 && nums[right] % 2 == 0) {// 交换int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}// 左指针移动if (nums[left] % 2 == 0) {left++;}// 右指针移动if (nums[right] % 2 == 1) {right--;}}*returnSize = numsSize;  // 设置返回的大小return nums;
}

数组是否存在重复元素

219. 存在重复元素 II - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {std::unordered_map<int, int> map;// 遍历数组for (int i = 0; i < nums.size(); ++i) {// 如果当前数字存在于哈希表中，检查索引差是否小于等于 kif (map.find(nums[i]) != map.end() && i - map[nums[i]] <= k) {return true;}// 更新数字的最后出现的索引map[nums[i]] = i;}return false;}
};

有序数组出现次数超过25%的元素

1287. 有序数组中出现次数超过25%的元素 - 力扣（LeetCode）

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

int findSpecialInteger(int* arr, int arrSize) {int threshold = arrSize / 4;  // 计算出现次数的阈值// 遍历数组，检查每个数字的连续出现次数for (int i = 0; i < arrSize; ++i) {int count = 1;  // 当前数字的出现次数// 计算当前数字的连续出现次数while (i + 1 < arrSize && arr[i] == arr[i + 1]) {count++;i++;}// 如果当前数字的出现次数超过阈值，返回该数字if (count > threshold) {return arr[i];}}return -1;  // 如果没有符合条件的数字，返回 -1（理论上不会出现这种情况）
}

有效的山脉数组

941. 有效的山脉数组 - 力扣（LeetCode）

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：

arr.length >= 3

在 0 < i < arr.length - 1 条件下，存在 i 使得：

arr[0] < arr[1] < ... arr[i-1] < arr[i]

arr[i] > arr[i+1] > ... > arr[arr.length - 1]

bool validMountainArray(int* arr, int arrSize) {// 长度必须至少为 3if (arrSize < 3) {return false;}int i = 0;// 找到递增的部分while (i + 1 < arrSize && arr[i] < arr[i + 1]) {i++;}// 山脉必须有递增和递减部分，且山峰不能在数组两端if (i == 0 || i == arrSize - 1) {return false;}// 找到递减的部分while (i + 1 < arrSize && arr[i] > arr[i + 1]) {i++;}// 如果 i 到达数组的末尾，说明递减部分有效return i == arrSize - 1;
}

最长连续递增序列

674. 最长连续递增序列 - 力扣（LeetCode）

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

int findLengthOfLCIS(int* nums, int numsSize) {if (numsSize == 0) return 0; // 如果数组为空，返回0int max_len = 1;      // 最长递增子序列的长度int current_len = 1;  // 当前递增子序列的长度for (int i = 1; i < numsSize; ++i) {if (nums[i] > nums[i - 1]) {// 当前元素比前一个元素大，递增子序列继续current_len++;} else {// 当前元素不大于前一个元素，更新最大长度，并重置当前递增长度max_len = (current_len > max_len) ? current_len : max_len;current_len = 1;  // 重置递增序列长度}}// 最后一个递增序列需要再次检查return (current_len > max_len) ? current_len : max_len;
}