上传网站到google,织梦手机网站怎么仿制,一个购物交易网站怎么做,科技网站设计公司有哪些恒大正式破产 准确来说#xff0c;是中国恒大#xff08;恒大汽车、恒大物业已于 2024-01-30 复牌#xff09;。 恒大破产#xff0c;注定成为历史的注目焦点。 作为首个宣布破产的房地产企业#xff0c;恒大的破产规模也创历史新高。 房地产作为曾推动中国三分之一经济增… 恒大正式破产 准确来说是中国恒大恒大汽车、恒大物业已于 2024-01-30 复牌。 恒大破产注定成为历史的注目焦点。 作为首个宣布破产的房地产企业恒大的破产规模也创历史新高。 房地产作为曾推动中国三分之一经济增长的行业恒大是当中毫无疑问的佼佼者。 能够成就这样的巨无霸自然是有时代和政策因素的。 在房地产行业的上升周期中房企普遍的高杠杆率和过度扩张如今成为一种回旋镖对各个层面都产生了影响。 即使你和我一样家里没有几套房没有买恒大的LW楼也没有持有恒大系股票但我们都感受到了这波的消费低迷和各行业的裁员潮这与房地产去泡沫化不无关系。 中国楼市基本对标美国股市当一个国家的重要经济载体出现问题失去信心普通人不可能独善其身。 当然了最幸福的人不会变。 仍然是那些无论房地产高歌猛进还是岌岌可危都自诩与他无关的人他觉得自己不考虑买房嘛能有啥关系。 我相信这批人和看到《游戏意见稿》就只讨论「该不该给氪金游戏充值」是同一批人。 随他们去吧。 ... 回归主线。 自上次写了米哈游的一面原题和变形题之后又有读者来投稿了。 据说这次是米哈游原神终面算法题。 看着确实像因为这是一道适合「由浅入深」的题目适合在面试过程中有来有回。 启动 题目描述 平台LeetCode 题号215 给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。 请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 的算法解决此问题。 示例 1: 输入: [3,2,1,5,6,4], k 2输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6], k 4输出: 4 提示 值域映射 树状数组 二分 除了直接对数组进行排序取第 位的 做法以外。 对于值域大小 小于 数组长度本身时我们还能使用「树状数组 二分」的 做法其中 为值域大小。 首先值域大小为 为了方便我们为每个 增加大小为 的偏移量将值域映射到 的空间。 将每个增加偏移量后的 存入树状数组考虑在 范围内进行二分假设我们真实第 大的值为 那么在以 为分割点的数轴上具有二段性质 在 范围内的数 满足「树状数组中大于等于 的数不低于 个」 在 范围内的数 不满足「树状数组中大于等于 的数不低于 个」 二分出结果后再减去刚开始添加的偏移量即是答案。 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(vectorint 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;}; 时间复杂度将所有数字放入树状数组复杂度为 二分出答案复杂度为 其中 为值域大小。整体复杂度为 空间复杂度 优先队列堆 另外一个容易想到的想法是利用优先队列堆由于题目要我们求的是第 大的元素因此我们建立一个小根堆。 根据当前队列元素个数或当前元素与栈顶元素的大小关系进行分情况讨论 当优先队列元素不足 个可将当前元素直接放入队列中 当优先队列元素达到 个并且当前元素大于栈顶元素栈顶元素必然不是答案可将当前元素放入队列中。 Java 代码 class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueueInteger 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(vectorint nums, int k) { priority_queueint, vectorint, greaterint 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] 时间复杂度 空间复杂度 快速选择 对于给定数组求解第 大元素且要求线性复杂度正解为使用「快速选择」做法。 基本思路与「快速排序」一致每次敲定一个基准值 x根据当前与 x 的大小关系将范围在 的 划分为到两边。 同时利用利用题目只要求输出第 大的值而不需要对数组进行整体排序我们只需要根据划分两边后第 大数会落在哪一边来决定对哪边进行递归处理即可。 ❝ 快速排序模板为面试向重点内容需要重要掌握。 ❞ 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: vectorint 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(vectorint _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);}; 时间复杂度期望 空间复杂度忽略递归带来的额外空间开销复杂度为 我是宫水三叶每天都会分享算法题解并和大家聊聊近期的所见所闻。 欢迎关注明天见。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 本文由 mdnice 多平台发布
