算法真题01 - 从n个数中等概率抽取m个数,抽奖程序
程序员文章站
2024-02-27 15:16:15
...
学习需要总结,今天抽空总结一下最近面试碰到的原题。
因为有些公司明确要求用c/c++,所以平时多练习c++,python暂时不写了。(我现在的想法:python用来高效率的开发或则深度学习;c++用来高性能的编程,刷题,量化交易等;java用来开发大型项目,前端后端框架等。目前以练习c++为主)
这些博客将以半日记半教程的形式出现,有缘的朋友可以看看,或提些意见;另外也当作自娱自乐,学习总结好了。
我觉得首先是思路,有了思路后需要练习编程能力,能不能把思路变成代码,面试时很多时候题目以前并没有见过。
第一题:从n个数中等概率抽取m个数,抽奖程序(baishanyunkeji,简单脱敏公司名,防止版权问题)
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
class Solution {
public:
vector<int> choujinag(int n, int m) {
vector<int> res;
vector<int> arr(n);
for (int i = 1; i <= n; i++)arr[i - 1] = i; //[1,2,..,n]
for(int length=n; length>=n-m+1; length--){
int idx = rand() % length + 0;
res.push_back(arr[idx]);
swap(arr[idx], arr[length - 1]);
}
return res;
}
};
int main()
{
Solution *solve = new Solution();
vector<int> res = solve->choujinag(10, 3);
for (auto x : res) {
cout << x << " ";
}
}
//2 9 7
面试时我直接用python,将选中的那个值pop出去,下一轮就不会选它了。面试官说pop会导致后面元素全部移动,让我想更优解,没想出。。。后来他告诉我答案了。
上一篇: 从m个数中取n个数
下一篇: 从n个数中删除m个数