JD 年终奖
今年以来，我们讲了不少关于「京东涨薪」的消息，以至于到了后期，我都觉得这是不是属于"空话"？
但今天，好消息来了。
京东方面正式颁布了《2024年年终奖发放计划通知》：
这简单的一张海报，信息量巨大，咱们一条条说。
首先是关于「年终奖的发放时间」，方案中提到：O 序列在年前（1月26日）会收到年终奖，而 P 序列则在一个月后（2月27号）收到年终奖。
这里其实就是说职级低的序列会在年前收到奖金，而职级相对高的序列则在年后。此举的主要作用应该是考虑到一线员工（快递员/销售/客服）更需要拿钱回家过年，也是值得点赞。
再之后的是更重磅的「奖金构成+奖金额度」信息，方案中提到会划分为「固定年终奖+目标年终奖」两部分。其中目标年终奖是拉开差距的主要来源，主要是根据绩效来判定。
绩效为 A+ 的员工获得 8 倍年终奖（全年 12+8=20 薪） 绩效为 A 的员工获得 6.5 倍年终奖（全年 12+6.5=18.5 薪） 绩效为 B+ 的员工获得 5 倍年终奖（全年 12+5=17 薪） 绩效为 B 的员工获得 3 倍年终奖（全年 12+3=15 薪）
现在剩下的，就看具体的 A+/A 的绩效占比会去到多少了。考虑到京东之前的涨薪通知，都会有一个平均数保底说明（例如全部门的平均年终奖不低于 18 薪），出岔子的可能性应该不大。感觉可以提前恭喜京东的同学们了。
对此，你怎么看？你司的年终奖机制是怎么样的？欢迎评论区交流。
...
回归主题。
来一道和「校招」相关的算法题。
题目描述
平台：LeetCode
题号：532
给定一个整数数组和一个整数 ，你需要在数组里找到 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
这里将 k-diff 数对定义为一个整数对 ，并满足下述全部条件：
0 <= i < j < nums.length|nums[i] - nums[j]| == k
注意，|val| 表示 val 的绝对值。
示例 1：
输入：nums = [3, 1, 4, 1, 5], k = 2
输出：2
解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。
示例 2：
输入：nums = [1, 2, 3, 4, 5], k = 1
输出：4
解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3：
输入：nums = [1, 3, 1, 5, 4], k = 0
输出：1
解释：数组中只有一个 0-diff 数对，(1, 1)。
提示：
哈希表
一个简单的想法是先使用「哈希表」进行计数。
对于每个 而言，根据 是否为 进行分情况讨论：
为 ：此时只能 组成数对，此时判断 出现次数是否大于 次，若满足则进行计数加一； 不为 ：此时 能够与 或 组成数对，分别查询 和 是否出现过，若出现过则进行计数加一。
为了防止相同的 进行重复计数，我们需要统计完 后，清空其出现次数。
Java 代码：
class Solution {
public int findPairs(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
int ans = 0;
for (int i : nums) {
if (map.get(i) == 0) continue;
if (k == 0) {
if (map.get(i) > 1) ans++;
} else {
int a = i - k, b = i + k;
if (map.getOrDefault(a, 0) > 0) ans++;
if (map.getOrDefault(b, 0) > 0) ans++;
}
map.put(i, 0);
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
unordered_map<int, int> map;
for (int i : nums) map[i]++;
int ans = 0;
for (int i : nums) {
if (map[i] == 0) continue;
if (k == 0) {
if (map[i] > 1) ans++;
} else {
int a = i - k, b = i + k;
if (map[a] > 0) ans++;
if (map[b] > 0) ans++;
}
map[i] = 0;
}
return ans;
}
};
时间复杂度： 空间复杂度：
离散化 + 二分
我们知道可以使用「数组」充当「哈希表」来减少常数，但由于 的值域大小为 ，可能会有 MLE 风险。
我们需要对 进行离散化，预处理出一个去重且有序的数组 list。
在统计答案时，我们不再需要在 nums 基础上统计，而可以直接在去重数组 list 上进行统计，同时将对「数值」的统计操作转换为对「下标」的统计操作。
Java 代码：
class Solution {
static int[] cnt = new int[10010];
List<Integer> list;
int find(int x) {
int n = list.size(), l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (list.get(mid) >= x) r = mid;
else l = mid + 1;
}
return list.get(r) == x ? r : -1;
}
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
list = new ArrayList<>();
for (int i : nums) {
if (list.isEmpty() || i != list.get(list.size() - 1)) list.add(i);
}
Arrays.fill(cnt, 0);
for (int i : nums) cnt[find(i)]++;
int ans = 0, idx = 0;
for (int i : list) {
if (k == 0) {
if (cnt[idx] > 1) ans++;
} else {
int a = find(i - k), b = find(i + k);
if (a != -1 && cnt[a] > 0) ans++;
if (b != -1 && cnt[b] > 0) ans++;
}
cnt[idx++] = 0;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int find(int x, const vector<int>& list) {
int n = list.size(), l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (list[mid] >= x) r = mid;
else l = mid + 1;
}
return list[r] == x ? r : -1;
}
int findPairs(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
vector<int> list;
for (int i : nums) {
if (list.empty() || i != list.back()) list.push_back(i);
}
unordered_map<int, int> cnt;
for (int i : nums) cnt[find(i, list)]++;
int ans = 0, idx = 0;
for (int i : list) {
if (k == 0) {
if (cnt[idx] > 1) ans++;
} else {
int a = find(i - k, list), b = find(i + k, list);
if (a != -1 && cnt[a] > 0) ans++;
if (b != -1 && cnt[b] > 0) ans++;
}
cnt[idx++] = 0;
}
return ans;
}
};
时间复杂度：排序离散化复杂度为 ，统计答案复杂度为 。整体复杂度为 空间复杂度：
离散化 + 双指针
跟进一步的，对于 而言，我们每次都在整段的 list 中二分找 和 的下标，导致我们统计 对答案的贡献时复杂度为 ，统计所有 对答案的贡献为 。
实际上，利用 list 本身的有序性，我们在从前往后处理每个 时，对应的 和 也必然是逐步增大，因此我们可以使用「双指针」来避免「二分」操作，使得统计所有 对答案贡献的复杂度从 下降到 。
Java 代码：
class Solution {
static int[] cnt = new int[10010];
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
List<Integer> list = new ArrayList<>();
for (int i : nums) {
if (list.isEmpty() || i != list.get(list.size() - 1)) list.add(i);
}
Arrays.fill(cnt, 0);
for (int i = 0, j = 0; i < nums.length; i++) {
if (nums[i] != list.get(j)) j++;
cnt[j]++;
}
int n = list.size(), idx = 0, ans = 0, l = 0, r = 0;
for (int i : list) {
if (k == 0) {
if (cnt[idx] > 1) ans++;
} else {
int a = i - k, b = i + k;
while (l < n && list.get(l) < a) l++;
while (r < n && list.get(r) < b) r++;
if (l < n && list.get(l) == a && cnt[l] > 0) ans++;
if (r < n && list.get(r) == b && cnt[r] > 0) ans++;
}
cnt[idx++] = 0;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
vector<int> list;
for (int i : nums) {
if (list.empty() || i != list.back()) list.push_back(i);
}
unordered_map<int, int> cnt;
for (int i = 0, j = 0; i < nums.size(); i++) {
if (nums[i] != list[j]) j++;
cnt[j]++;
}
int n = list.size(), idx = 0, ans = 0, l = 0, r = 0;
for (int i : list) {
if (k == 0) {
if (cnt[idx] > 1) ans++;
} else {
int a = i - k, b = i + k;
while (l < n && list[l] < a) l++;
while (r < n && list[r] < b) r++;
if (l < n && list[l] == a && cnt[l] > 0) ans++;
if (r < n && list[r] == b && cnt[r] > 0) ans++;
}
cnt[idx++] = 0;
}
return ans;
}
};
时间复杂度：排序离散化复杂度为 ，统计答案复杂度为 ，整体复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
