米哈游（原神）终面算法原题

2024-01-31 06:28
文章标签 算法 原神 米哈 终面 原题

本文主要是介绍米哈游（原神）终面算法原题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

恒大正式破产

准确来说，是中国恒大（恒大汽车、恒大物业已于 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(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;
};
  • 时间复杂度：将所有数字放入树状数组复杂度为 ；二分出答案复杂度为 ，其中 为值域大小。整体复杂度为
  • 空间复杂度：

优先队列（堆）

另外一个容易想到的想法是利用优先队列（堆），由于题目要我们求的是第 大的元素，因此我们建立一个小根堆。

根据当前队列元素个数或当前元素与栈顶元素的大小关系进行分情况讨论：

  • 当优先队列元素不足 个，可将当前元素直接放入队列中；
  • 当优先队列元素达到 个，并且当前元素大于栈顶元素（栈顶元素必然不是答案），可将当前元素放入队列中。

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]
  • 时间复杂度：
  • 空间复杂度：

快速选择

对于给定数组，求解第 大元素，且要求线性复杂度，正解为使用「快速选择」做法。

基本思路与「快速排序」一致，每次敲定一个基准值 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:
    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);
};
  • 时间复杂度：期望
  • 空间复杂度：忽略递归带来的额外空间开销，复杂度为

我是宫水三叶，每天都会分享算法题解，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台发布

这篇关于米哈游（原神）终面算法原题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/662844。

相关文章

openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2