在不同大厂之间跳槽，对于互联网人来说是习以为常的事。每年那点普调，哪有一次 20%~30% 的跳槽涨幅来得实在？但收入只是硬币的一面，适应新公司环境、融入不同团队文化，又是另一回事了。
我一直想做个统计——哪个公司的员工“想吃后悔药”的最多？从一家公司出来后，有多少人会怀念老东家？如果有这份名单，字节跳动大概率会名列前茅。
这不，脉脉上就刷到一篇近期的帖子：一位前字节员工在字节同事圈里直言——“真的想回流了，外面没那么好玩。”
评论区有人问得很直接：真能回流吗？楼主给了肯定答复——能回，但需要经过漫长的准备，因为回流也得走完整的“笔试+面试”流程。
更扎心的是，有网友提醒：虽然是回流，但本质上你还是“新员工”，回来很容易试用期不通过，或者背上绩效压力。不少人觉得，既然走了就没必要回来，甚至用“大逃杀”来形容，认为社招进来的新人本来就很难适应。
其实，这种情况并非字节一家独有。其他大厂，甚至你跳去的新公司，同样存在类似的问题——新人在哪儿都不容易。即便如此，依然有不少和楼主经历相似的人萌生了“回流”的念头。有的前字节员工当初领了礼包（N+1），现在去了快手，还是想回到总部。
也有人真的走了“回流”这条路，而且已经成功拿到了字节的 Offer。
后台经常收到读者求助：“我该不该跳槽？跳了再回流不方便怎么办？”我只能说，在不同时期做对的事情就好。该跳就跳，但回流的路也尽量别给自己堵死——别和前公司 HR 闹得太僵。很多时候，你出去一遭再回来，未必是坏事，至少薪资会有新的变化。
对此，你怎么看？你有过回流的念头吗？想回流的公司是哪家？欢迎评论区聊聊。更多职场杂谈、开发者圈子的冷暖故事，也欢迎来云栈开发者广场分享~
题目描述
平台：LeetCode
题号：215
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
注意：你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
必须设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
- $1 \le k \le$ nums.length $\le 10^5$
- $-10^4 \le$ nums[i] $\le 10^4$
值域映射 + 树状数组 + 二分
除了直接对数组排序、取第 $k$ 位的 $O(n\log n)$ 做法，当值域大小小于数组长度本身时，我们还可以使用“树状数组 + 二分”的 $O(n\log C)$ 做法，其中 $C$ 为值域大小。
首先值域大小为 $2\times 10^4$，为了方便，我们为每个数增加大小为 $10^5$ 的偏移量，将值域映射到 $[0, 2\times 10^5]$ 的空间。将每个增加偏移量后的元素存入树状数组，然后在 $[0, 2\times 10^5]$ 范围内进行二分。假设真实第 $k$ 大的值为 $t$，那么在以 $t$ 为分割点的数轴上，具有二段性质：
- 在 $[t, 2\times 10^5]$ 范围内的数满足“树状数组中大于等于 $t$ 的数不低于 $k$ 个”
- 在 $[0, t-1]$ 范围内的数不满足上述条件
二分出结果后再减去偏移量即是答案。
Java 代码：
class Solution {
int M = 100010, N = 2 * M;
int[] tr = new int[N];
int lowbit(int x) {
return x & -x;
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
void add(int x) {
for (int i = x; i < N; i += lowbit(i)) tr[i]++;
}
public int findKthLargest(int[] nums, int k) {
for (int x : nums) add(x + M);
int l = 0, r = N - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (query(N - 1) - query(mid - 1) >= k) l = mid;
else r = mid - 1;
}
return r - M;
}
}
C++ 代码：
class Solution {
public:
int N = 200010, M = 100010, tr[200010];
int lowbit(int x) {
return x & -x;
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
void add(int x) {
for (int i = x; i < N; i += lowbit(i)) tr[i]++;
}
int findKthLargest(vector<int>& nums, int k) {
for (int x : nums) add(x + M);
int l = 0, r = N - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (query(N - 1) - query(mid - 1) >= k) l = mid;
else r = mid - 1;
}
return r - M;
}
};
Python 代码：
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
N, M = 200010, 100010
tr = [0] * N
def lowbit(x):
return x & -x
def query(x):
ans = 0
i = x
while i > 0:
ans += tr[i]
i -= lowbit(i)
return ans
def add(x):
i = x
while i < N:
tr[i] += 1
i += lowbit(i)
for x in nums:
add(x + M)
l, r = 0, N - 1
while l < r:
mid = l + r + 1 >> 1
if query(N - 1) - query(mid - 1) >= k:
l = mid
else:
r = mid - 1
return r - M
TypeScript 代码：
function findKthLargest(nums: number[], k: number): number {
const N = 200010, M = 100010;
const tr = new Array(N).fill(0);
const lowbit = function(x: number): number {
return x & -x;
};
const add = function(x: number): void {
for (let i = x; i < N; i += lowbit(i)) tr[i]++;
};
const query = function(x: number): number {
let ans = 0;
for (let i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
};
for (const x of nums) add(x + M);
let l = 0, r = N - 1;
while (l < r) {
const mid = l + r + 1 >> 1;
if (query(N - 1) - query(mid - 1) >= k) l = mid;
else r = mid - 1;
}
return r - M;
};
- 时间复杂度：将所有数字放入树状数组复杂度为 $O(n\log C)$；二分出答案复杂度为 $O(\log C)$，其中 $C$ 为值域大小。整体复杂度为 $O(n\log C)$
- 空间复杂度：$O(C)$
优先队列（堆）
另一个容易想到的思路是使用优先队列（堆）。题目要求第 $k$ 大的元素，因此我们建立一个小根堆。根据当前队列元素个数以及当前元素与堆顶元素的大小关系进行分情况讨论：
- 当优先队列元素不足 $k$ 个，可将当前元素直接放入队列；
- 当优先队列元素达到 $k$ 个，且当前元素大于堆顶元素（堆顶必然不是答案），则将当前元素放入队列中，并弹出堆顶。
Java 代码：
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
for (int x : nums) {
if (q.size() < k || q.peek() < x) q.add(x);
if (q.size() > k) q.poll();
}
return q.peek();
}
}
C++ 代码：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> q;
for (int x : nums) {
if (q.size() < k || q.top() < x) q.push(x);
if (q.size() > k) q.pop();
}
return q.top();
}
};
Python 代码：
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
q = []
for x in nums:
if len(q) < k or q[0] < x:
heapq.heappush(q, x)
if len(q) > k:
heapq.heappop(q)
return q[0]
- 时间复杂度：$O(n\log k)$
- 空间复杂度：$O(k)$
快速选择
对于给定数组，求解第 $k$ 大元素且要求线性复杂度，正解为使用“快速选择”算法。基本思路与快速排序一致：每次选定一个基准值 x，根据元素与 x 的大小关系，将区间 $[l, r]$ 内的元素划分到两边。同时利用题目只要求输出第 $k$ 大的值，而不需要完整排序，我们只需根据划分后第 $k$ 大数落在哪一边，来决定递归处理哪一侧即可。
快速排序模板是面试重点内容，需要重点掌握。
Java 代码：
class Solution {
int[] nums;
int qselect(int l, int r, int k) {
if (l == r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(i, j);
}
if (k <= j) return qselect(l, j, k);
else return qselect(j + 1, r, k);
}
void swap(int i, int j) {
int c = nums[i];
nums[i] = nums[j];
nums[j] = c;
}
public int findKthLargest(int[] _nums, int k) {
nums = _nums;
int n = nums.length;
return qselect(0, n - 1, n - k);
}
}
C++ 代码：
class Solution {
public:
vector<int> nums;
int qselect(int l, int r, int k) {
if (l == r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(nums[i], nums[j]);
}
if (k <= j) return qselect(l, j, k);
else return qselect(j + 1, r, k);
}
int findKthLargest(vector<int>& _nums, int k) {
nums = _nums;
int n = nums.size();
return qselect(0, n - 1, n - k);
}
};
Python 代码：
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def qselect(l, r, k):
if l == r:
return nums[k]
x, i, j = nums[l], l - 1, r + 1
while i < j:
i += 1
while nums[i] < x:
i += 1
j -= 1
while nums[j] > x:
j -= 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
if k <= j:
return qselect(l, j, k)
else:
return qselect(j + 1, r, k)
n = len(nums)
return qselect(0, n - 1, n - k)
TypeScript 代码：
function findKthLargest(nums: number[], k: number): number {
const qselect = function(l: number, r: number, k: number): number {
if (l === r) return nums[k];
const x = nums[l];
let i = l - 1, j = r + 1;
while (i < j) {
i++;
while (nums[i] < x) i++;
j--;
while (nums[j] > x) j--;
if (i < j) [nums[i], nums[j]] = [nums[j], nums[i]];
}
if (k <= j) return qselect(l, j, k);
else return qselect(j + 1, r, k);
};
const n = nums.length;
return qselect(0, n - 1, n - k);
};
- 时间复杂度：期望 $O(n)$
- 空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$
发表于 1 小时前
|
查看: 2|
回复: 0
