目录
100285. 找出与数组相加的整数 I
原题链接
思路分析
题目保证有解,签到题直接排序就行
AC代码
class Solution:
def addedInteger(self, nums1: List[int], nums2: List[int]) -> int:
nums1.sort()
nums2.sort()
return nums2[0] - nums1[0]
100287. 找出与数组相加的整数 II
原题链接
思路分析
小范围考虑直接暴力,枚举x
时间复杂度O(1000 * n)
AC代码
class Solution:
def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
i = -1000
st = Counter(nums2)
while True:
s = Counter([x + i for x in nums1]) & st
if s == st:
return i
i += 1
return i
100282. 数组最后一个元素的最小值
原题链接
思路分析
就是在x的二进制表示下,从低到高在0的位上依次插入n - 1的二进制位
时间复杂度O(logn)
AC代码
class Solution {
public:
typedef long long LL;
static constexpr LL N = 50;
long long minEnd(int n, int x) {
string sub = bitset<N>(n - 1).to_string();
string s = bitset<N>(x).to_string();
reverse(sub.begin(), sub.end());
reverse(s.begin(), s.end());
LL ret = 0;
int sz = 0, t = n - 1;
while(t) sz ++, t >>= 1;
for(int i = 0, j = 0; j < sz; i ++)
if(s[i] == '0') s[i] = sub[j ++];
for(int i = 0; i < N; i ++)
if(s[i] == '1') ret += 1LL << i;
return ret;
}
};
100257. 找出唯一性数组的中位数
原题链接
思路分析
二分+滑窗
数据量提示我们用nlogn的方式,再加上统计区间内元素个数会想到滑窗
然后想到滑窗越大,区间内元素个数越大,换言之给定x,x越大,满足区间内元素个数不超过x的区间越多
然后逻辑更进一步思考枚举二分答案能否设计出check函数
考虑二分答案mid,代表目标值,然后如果原数组满足区间内元素个数不超过mid的区间数目大于等于 (n - 1) * n / 2 + (n * (n - 1)) & 1(这个是中位数位置),那么r = mid
否则l = mid + 1
注意写unordered_map的时候不要写成map了,不然就过不了,数据还是蛮强的,nlog^2n过不了
AC代码
class Solution {
public:
long long n, L, R, m, tot;
bool check(int x, vector<int>& a){
long long ret = 0;
unordered_map<int, int> mp;
int l = 0, r = 0;
for(; r < n; r ++){
mp[a[r]] ++;
if(mp.size() > x){
while(mp.size() > x){
ret += r - l;
mp[a[l]] --;
if(!mp[a[l]]) mp.erase(a[l]);
l ++;
}
}
if(ret >= m) return true;
}
while(l < n)
ret += r - l, l ++;
return ret >= m;
}
int medianOfUniquenessArray(vector<int>& a) {
n = a.size();
L = 1, R = n, tot = (1 + n) * n / 2;
m = tot / 2 + (tot & 1);
while(L < R){
int mid = L + R >> 1;
if(check(mid, a)) R = mid;
else L = mid + 1;
}
return L;
}
};