题目
找出与数组相加的整数 I
给你两个长度相等的数组nums1和nums2。
数组nums1中的每个元素都与变量x所表示的整数相加。如果x为负数，则表现为元素值的减少。
在与x相加后，nums1和nums2相等。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组相等。
返回整数x。
示例：
输入：nums1=[2,6,4],nums2=[9,7,5]
输出：3
解释：
与3相加后，nums1和nums2相等。
解题思路
根据题意能得出x=min(nums2)-min(nums1)
class Solution {
public int addedInteger(int[] nums1, int[] nums2) {
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
for (int i = 0; i < nums1.length; i++) {
min1 = Math.min(min1, nums1[i]);
min2 = Math.min(min2, nums2[i]);
}
return min2 - min1;
}
}
找出与数组相加的整数 II
给你两个整数数组nums1和nums2。
从nums1中移除两个元素，并且所有其他元素都与变量x所表示的整数相加。如果x为负数，则表现为元素值的减少。
执行上述操作后，nums1和nums2相等。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组相等。
返回能够实现数组相等的最小整数x。
示例：
输入：nums1=[4,20,16,12,8],nums2=[14,18,10]
输出：-2
解释：
移除nums1中下标为[0,4]的两个元素，并且每个元素与-2相加后，nums1变为[18,14,10]，与nums2相等。
解题思路
O(nlogn) 排序+判断子序列
class Solution {
public int minimumAddedInteger(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
// 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
// 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
for (int i = 2; i > 0; i--) {
int diff = nums2[0] - nums1[i];
// 在 {nums1[i] + diff} 中找子序列 nums2
int j = 0;
for (int k = i; k < nums1.length; k++) {
if (j < nums2.length && nums2[j] == nums1[k] + diff && ++j == nums2.length) {
// nums2 是 {nums1[i] + diff} 的子序列
return diff;
}
}
}
// 题目保证答案一定存在
return nums2[0] - nums1[0];
}
}
数组最后一个元素的最小值
给你两个整数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。
解题思路
位运算
class Solution {
public long minEnd(int n, int x) {
n--; // 先把 n 减一，这样下面讨论的 n 就是原来的 n-1
long ans = x;
int i = 0, j = 0;
while ((n >> j) > 0) {
// x 的第 i 个比特值是 0，即「空位」
if ((ans >> i & 1) == 0) {
// 空位填入 n 的第 j 个比特值
ans |= (long) (n >> j & 1) << i;
j++;
}
i++;
}
return ans;
}
}
找出唯一性数组的中位数
给你一个整数数组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 。
解题思路
二分答案+滑动窗口
class Solution {
public int medianOfUniquenessArray(int[] nums) {
int n = nums.length;
long k = ((long) n * (n + 1) / 2 + 1) / 2;
int left = 0;
int right = n;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (check(nums, mid, k)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
private boolean check(int[] nums, int upper, long k) {
long cnt = 0;
int l = 0;
HashMap<Integer, Integer> freq = new HashMap<>();
for (int r = 0; r < nums.length; r++) {
freq.merge(nums[r], 1, Integer::sum);
while (freq.size() > upper) {
int out = nums[l++];
if (freq.merge(out, -1, Integer::sum) == 0) {
freq.remove(out);
}
}
cnt += r - l + 1;
if (cnt >= k) {
return true;
}
}
return false;
}
}