leetcode weekly contest 395

T4 确实是个好题目，前 3 题比较简单。

100285. 找出与数组相加的整数 I

给你两个长度相等的数组 nums1 和 nums2。

数组 nums1 中的每个元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

在与 x 相加后，nums1 和 nums2 相等。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组相等。

返回整数 x 。

示例 1:

输入：nums1 = [2,6,4], nums2 = [9,7,5]

输出：3

解释：

与 3 相加后，nums1 和 nums2 相等。

示例 2:

输入：nums1 = [10], nums2 = [5]

输出：-5

解释：

与 -5 相加后，nums1 和 nums2 相等。

示例 3:

输入：nums1 = [1,1,1,1], nums2 = [1,1,1,1]

输出：0

解释：

与 0 相加后，nums1 和 nums2 相等。

提示：

1 <= nums1.length == nums2.length <= 100
0 <= nums1[i], nums2[i] <= 1000
测试用例以这样的方式生成：存在一个整数 x，使得 nums1 中的每个元素都与 x 相加后，nums1 与 nums2 相等。

地址

https://leetcode.cn/contest/weekly-contest-395/problems/find-the-integer-added-to-array-i/

题意

直接模拟

思路

排序后，直接取两个数组中的最小值之差即可。
复杂度分析：

时间复杂度：$O(n\log n)$。
空间复杂度：$O(1)$。

代码

class Solution:
    def addedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        return min(nums2) - min(nums1)

impl Solution {
    pub fn added_integer(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let min_nums1 = nums1.iter().min().unwrap();
        let min_nums2 = nums2.iter().min().unwrap();
        min_nums2 - min_nums1
    }
}

100287. 找出与数组相加的整数 II

给你两个整数数组 nums1 和 nums2。

从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

执行上述操作后，nums1 和 nums2 相等。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组相等。

返回能够实现数组相等的最小整数 x 。

示例 1:

输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]

输出：-2

解释：

移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2 相等。

示例 2:

输入：nums1 = [3,5,5,3], nums2 = [7,7]

输出：2

解释：

移除 nums1 中下标为 [0,3] 的两个元素，并且每个元素与 2 相加后，nums1 变为 [7,7] ，与 nums2 相等。

提示：

3 <= nums1.length <= 200
nums2.length == nums1.length - 2
0 <= nums1[i], nums2[i] <= 1000
测试用例以这样的方式生成：存在一个整数 x，nums1 中的每个元素都与 x 相加后，再移除两个元素，nums1 可以与 nums2 相等。

地址

https://leetcode.cn/contest/weekly-contest-395/problems/find-the-integer-added-to-array-ii/

题意

模拟，枚举

思路

先对两个数组排序之后，此时我们枚举从 $nums1$ 中剔除的两个元素，$nums1$ 中剩余的元素则依次按从小到大与 $nums2$ 中的元素进行相减，检测相减的结果是否相等即可。
复杂度分析：

时间复杂度：$O(n^3)$，其中 $n$ 表示给定的数组的长度。
空间复杂度：$O(1)$。

代码

class Solution:
    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        nums1.sort()
        nums2.sort()
        res = inf
        for i in range(n):
            for j in range(i + 1, n):
                diff, valid = inf, True
                s = 0
                for k in range(n):
                    if k == i or k == j:
                        continue
                    x = nums2[s] - nums1[k]
                    if diff == inf:
                        diff = x
                    elif diff != x:
                        valid = False
                        break
                    s += 1
                if valid:
                    res = min(res, diff)
        return res

impl Solution {
    pub fn minimum_added_integer(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut nums1 = nums1;
        let mut nums2 = nums2;
        nums1.sort_unstable();
        nums2.sort_unstable();
        let n = nums1.len();
        let mut res = i32::MAX;

        for i in 0..n {
            for j in (i + 1)..n {
                let mut diff = i32::MAX;
                let mut valid = true;
                let mut s = 0;

                for k in 0..n {
                    if k == i || k == j {
                        continue;
                    }

                    let x = nums2[s] - nums1[k];
                    if diff == i32::MAX {
                        diff = x;
                    } else if diff != x {
                        valid = false;
                        break;
                    }
                    s += 1;
                }

                if valid {
                    res = res.min(diff);
                }
            }
        }

        res
    }
}

100282. 数组最后一个元素的最小值

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

返回 nums[n - 1] 可能的最小值。

示例 1：

输入：n = 3, x = 4

输出：6

解释：

数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。

示例 2：

输入：n = 2, x = 7

输出：15

解释：

数组 nums 可以是 [7,15] ，最后一个元素为 15 。

提示：

1 <= n, x <= 108

地址

https://leetcode.cn/contest/weekly-contest-395/problems/minimum-array-end/

题意

数学

思路

根据 $and$ 的规则，此时生成的数组中的第一个元素肯定是 $x$，$x$ 的所有二进制位上是 $1$ 的全都无法改变，此时只能增加 $x$ 的二进制位上是 $0$ 的数位，此时我们直接从小到大生成 $n-1$ 个数即可，相当于除去 $x$ 二进制位上为 $1$ 的部分，然后填充 $n-1$ 即可。
复杂度：

时间复杂度：$O(\log x + n)$，其中 $x,n$ 表示给定的元素；
空间复杂度：$O(1)$；

代码

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        res, j = 0, 0
        n -= 1
        for i in range(63):
            if (x & (1 << i)) != 0:
                res |= (1 << i)
            else:
                if (n & (1 << j)) != 0:
                    res |= (1 << i)
                j += 1
        return res

100257. 找出唯一性数组的中位数

给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有非空子数组中不同元素的个数。

换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。

其中，distinct(nums[i..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。

返回 nums 唯一性数组 的 中位数 。

注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

示例 1：

输入：nums = [1,2,3]

输出：1

解释：

nums 的唯一性数组为 [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。

示例 2：

输入：nums = [3,4,3,4,5]

输出：2

解释：

nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

示例 3：

输入：nums = [4,3,5,4]

输出：2

解释：

nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105

地址

https://leetcode.cn/contest/weekly-contest-395/problems/find-the-median-of-the-uniqueness-array/

题意

二分查找

思路

直接统计的话发现很麻烦，但是我们有个问题我们很容易求出，即求当前数组中连续子数组中元素个数小于等于 $x$ 的数目，这个问题我们知道可以用二分查找或者滑动窗口很容易求出，此时我们知道对于长度为 $n$ 的数组，则其连续的子数组的数目为 $\dfrac{n \times (n+1)}{2}$，假设当前给定的长度为 $x$，此时我们只需要统计出当前数组中连续子数组中元素出现次数小于等于 $x$ 的数目，我们很容易统计出，假设以当前 $nums[i]$ 为结尾的子数组，次数我们只需要移动 $j$ 使得窗口内 $[j,i]$ 中元素出现的次数刚好小于等于 $x$ 即可，实际可以参考每个子数组的数字种类数。
复杂度分析:

时间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度；
空间复杂度：$O(1)$；

代码

class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        n = len(nums)
        lo, hi = 1, n
        median = (n * (n + 1) // 2 + 1) // 2
        res = 0
        
        def check(x):
            cnt = Counter()
            j, tot = 0, 0
            for i, v in enumerate(nums):
                cnt[v] += 1
                while len(cnt) > x:
                    cnt[nums[j]] -= 1
                    if cnt[nums[j]] == 0:
                        del cnt[nums[j]]
                    j += 1
                tot += i - j + 1
            return tot >= median
        
        while lo <= hi:
            mid = (lo + hi) // 2
            if check(mid):
                res = mid
                hi = mid - 1
            else:
                lo = mid + 1

        return res

use std::collections::HashMap;

impl Solution {
    pub fn median_of_uniqueness_array(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i64;
        let median = ((n * (n  + 1) / 2 + 1) / 2) as i64;
        let mut res = 0;
        let mut lo = 1;
        let mut hi = n as i32;

        fn check(nums: &[i32], x: usize, median: i64) -> bool {
            let mut cnt: HashMap<i32, i32> = HashMap::new();
            let mut j = 0;
            let mut tot = 0 as i64;

            for (i, &v) in nums.iter().enumerate() {
                *cnt.entry(v).or_insert(0) += 1;
                while cnt.len() > x {
                    *cnt.entry(nums[j]).or_insert(0) -= 1;
                    if *cnt.get(&nums[j]).unwrap_or(&0) == 0 {
                        cnt.remove(&nums[j]);
                    }
                    j += 1;
                }
                tot += (i - j + 1) as i64;
            }
            tot >= median
        }

        while lo <= hi {
            let mid = (lo + hi) / 2;
            if check(&nums, mid as usize, median) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        res
    }
}

欢迎关注和打赏，感谢支持！

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 哪些奋斗者

Tags: 题解力扣周赛赛

← leetcode contest 394 leetcode biweekly contest 129 →

扫描二维码，分享此文章