1980-找出不同的二进制字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为
n 且 没有出现 在 nums 中的二进制字符串 。 如果存在多种答案，只需返回 任意一个 即可。

示例 1：

**输入：** nums = ["01","10"]
**输出：** "11"
**解释：** "11" 没有出现在 nums 中。"00" 也是正确答案。

示例 2：

**输入：** nums = ["00","01"]
**输出：** "11"
**解释：** "11" 没有出现在 nums 中。"10" 也是正确答案。

示例 3：

**输入：** nums = ["111","011","001"]
**输出：** "101"
**解释：** "101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。

提示：

  • n == nums.length
  • 1 <= n <= 16
  • nums[i].length == n
  • nums[i] 为 '0' 或 '1'
  • nums 中的所有字符串 互不相同

方法一：转化为整数

思路与算法

我们可以将长度为 n 的二进制字符串看作 [0, 2^n - 1] 闭区间内正整数的二进制表示，这样就建立起了字符串和整数之间的一一映射。

我们可以将 nums 中所有字符串转化为对应的整数放在哈希集合中。由于该哈希集合中有 n 个元素，因此根据鸽巢原理，在 [0, n] 闭区间的 n + 1 个整数中一定存在一个整数，它不在该哈希集合中。换言之，该整数对应的字符串一定没有在 nums 中出现。

因此，在预处理哈希集合后，我们只需要遍历 [0, n] 闭区间中的整数，当找到第一个不在哈希集合中的整数时，我们将它转化为对应的二进制字符串返回即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        // 预处理对应整数的哈希集合
        unordered_set<int> vals;
        for (const string& num : nums){
            vals.insert(stoi(num, nullptr, 2));
        }
        // 寻找第一个不在哈希集合中的整数
        int val = 0;
        while (vals.count(val)){
            ++val;
        }
        // 将整数转化为二进制字符串返回
        return bitset<16>(val).to_string().substr(16 - n, 16);
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        # 预处理对应整数的哈希集合
        vals = {int(num, 2) for num in nums}
        # 寻找第一个不在哈希集合中的整数
        val = 0
        while val in vals:
            val += 1
        # 将整数转化为二进制字符串返回
        res = "{:b}".format(val)
        return '0' * (n - len(res)) + res

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 为 nums 的长度。预处理哈希集合的时间复杂度为 O(n^2)，寻找第一个不在哈希表中的整数与生成答案字符串的时间复杂度为 O(n)。

  • 空间复杂度：O(n)，即为哈希集合的空间复杂度。

 Comments
On this page
1980-找出不同的二进制字符串