当前位置：首页 > article >正文

LeetCode 349: 两个数组的交集

article 2025/2/1 10:43:48

LeetCode 349: 两个数组的交集 - C语言

问题描述

给定两个数组 ransomNote 和 magazine，你需要判断 ransomNote 是否可以由 magazine 里的字符构成。每个字符可以使用一次。

解题思路

通过统计 magazine 中每个字符的频次，并与 ransomNote 中字符的需求频次进行比对，最终判断 magazine 中的字符是否足够构建 ransomNote。

代码实现

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool canConstruct(char* ransomNote, char* magazine) {
    // 定义一个长度为26的数组，用来记录字符出现的频次
    int hasmap[26] = {0}; 

    // 遍历 ransomNote 字符串，减少对应字母的频次
    for (int i = 0; i < strlen(ransomNote); i++) {
        hasmap[ransomNote[i] - 'a'] -= 1;  // 对应字母的频次减1
    }

    // 遍历 magazine 字符串，增加对应字母的频次
    for (int i = 0; i < strlen(magazine); i++) {
        hasmap[magazine[i] - 'a'] += 1;  // 对应字母的频次加1
    }

    // 最后检查 hasmap 中每个位置的值，确保没有负值
    for (int i = 0; i < 26; i++) {
        if (hasmap[i] < 0) return false;  // 如果某个字母的频次小于0，返回false
    }
    
    return true;  // 所有检查通过，返回true
}

int main() {
    char ransomNote[] = "aabb";
    char magazine[] = "abbbcca";
    
    if (canConstruct(ransomNote, magazine)) {
        printf("可以构成\n");
    } else {
        printf("无法构成\n");
    }

    return 0;
}

逐行解释

1. 初始化字符频次数组

int hasmap[26] = {0};

这行代码定义了一个大小为 26 的整型数组 hasmap，用于记录每个字母出现的频次。hasmap[i] 表示字母 a + i 的频次。初始化时，所有字母的频次为 0。

2. 遍历 `ransomNote` 字符串，减少字符频次

for (int i = 0; i < strlen(ransomNote); i++) {
    hasmap[ransomNote[i] - 'a'] -= 1;
}

在这个循环中，我们遍历 ransomNote 中的每个字符，将相应字符的频次减少 1。通过 ransomNote[i] - 'a' 可以将字符转换为其对应的索引位置。例如，字符 'a' 对应 0，字符 'b' 对应 1，依此类推。

3. 遍历 `magazine` 字符串，增加字符频次

for (int i = 0; i < strlen(magazine); i++) {
    hasmap[magazine[i] - 'a'] += 1;
}

在这一步，我们遍历 magazine 中的每个字符，将相应字符的频次增加 1。这样，hasmap 数组会记录 magazine 中每个字母的出现次数。

4. 检查是否所有字符的频次都满足需求

for (int i = 0; i < 26; i++) {
    if (hasmap[i] < 0) return false;
}

此处，我们遍历 hasmap 数组，检查是否有任何字符的频次小于 0。如果存在这样的情况，说明 magazine 中的某个字母的数量不足以构建 ransomNote，因此返回 false。

5. 返回结果

return true;

如果所有字符的频次都满足需求，最终返回 true，表示 magazine 可以用来构建 ransomNote。

时间复杂度分析

遍历 ransomNote 和 magazine 的时间复杂度为 $O (n + m)$ ，其中 $n$ 和 $m$ 分别是 ransomNote 和 magazine 的长度。
遍历 hasmap 数组的时间复杂度为 $O (26) = O (1)$ ，因为数组的大小是固定的。

因此，总的时间复杂度是 $O (n + m)$ ，其中 $n$ 和 $m$ 是输入字符串的长度。

空间复杂度分析

使用了一个大小为 26 的数组来记录字符频次，空间复杂度为 $O (1)$ ，即常数空间。

测试用例

int main() {
    char ransomNote[] = "aabb";
    char magazine[] = "abbbcca";
    
    if (canConstruct(ransomNote, magazine)) {
        printf("可以构成\n");
    } else {
        printf("无法构成\n");
    }

    return 0;
}