leetcode 第 395 场算法比赛

零、背景

这次比赛是调休日，需要加班，所以没有参加比赛，晚上做了一下题，最后一题有点难度。

A: 排序。
B: 枚举。
C: 位运算。
D: 二分+双指针。

排名：无 代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/3/395

一、找出与数组相加的整数 I

题意：给两个数组，确定两个数组的所有元素相差 X，求这个X。

思路：两个数组排序，第一个元素的差就是整个数组的差。

二、找出与数组相加的整数 II

题意：给两个数组，第一个数组比第二个多两个元素，删除某两个元素后，两个数组满足所有元素相差 X，求最小的 X。

思路1：枚举两个元素，判断剩余的元素是否满足都相差 X。
复杂度：O(n^3)

思路2：枚举最小值，确定差值 X，判断是否有答案。
复杂度：O(n log) + O(n)

三、数组最后一个元素的最小值

题意：求构造一个数组，数组递增，所有值与运算后是 X。

思路：与运算后都是 X，说明所有元素都有 X 的二进制 1。
不考虑这些二进制 1，剩余的位合并在一起，需要递增，即为 1~n。

之后把 X 的二进制插入到 n 即可。

四、找出唯一性数组的中位数

题意：给一个数组，所有子数组去重后的个数组成新的有序数组，问中位数值是多少？

思路：二分答案 V，则问题转化为了求子数组去重后元素个数小于等于 V 的个数。

如果把题意修改为子数组和小于等于 V，我们很容易使用双指针来做这道题。
如果我们有一个数据结构，可以快速维护去重后元素个数，即可使用双指针来做这道题。

这样的数据结构很容易想到，使用带计数的平衡树即可，常用的数据结构是 map。
实现方法与子数组和完全一样。

复杂度：O(n log(n) log(n))

五、最后

这次比赛最后一题滑动窗口不容易想到，但是多想想也能想到，你学会了吗？

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code