[CareerCup] 18.3 Randomly Generate Integers 무작위 숫자 생성
18.3 Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.
이 문제는 우리가 한 수조에서 m개의 숫자를 무작위로 추출하도록 한다. 모든 숫자가 추출될 확률이 같도록 요구한다. 사실 이 문제는 이전의 18.2 Shuffle Cards의 방법을 사용한다. 마찬가지로 우리는 귀속과 교체 두 가지 방법으로 할 수 있다. 귀속의 사고방식은 역소법으로 i+1=m로 거슬러 올라갈 때 수조의 앞 m개의 숫자를 추출하여 결과res에 넣고 한 층씩 되돌아온다.돌아오는 과정에서 매번 [0,i] 사이에서 무작위 수를 꺼낸 다음에 이 수가 m보다 작으면res[k]의 값은nums[i]로 업데이트합니다. 이것은 카드를 씻는 것과 같습니다. 이렇게 하면 모든 수가 꺼질 확률이 같습니다. 코드는 다음과 같습니다.
해법 1:
vector<int> pick(vector<int> &nums, int m, int i) {
if (i + 1 < m) return {};
else if (i + 1 == m) {
vector<int> res(m);
for (int k = 0; k < m; ++k) {
res[k] = nums[k];
}
return res;
} else {
vector<int> res = pick(nums, m, i - 1);
int k = rand() % (i + 1);
if (k < m) res[k] = nums[i];
return res;
}
}물론 대응하는 교체된 묘사법도 있다. 사고방식은 모두 같다.
해법 2:
vector<int> pick(vector<int> &nums, int m) {
vector<int> res(m);
for (int i = 0; i < m; ++i) {
res[i] = nums[i];
}
for (int i = m; i < nums.size(); ++i) {
int k = rand() % (i + 1);
if (k < m) res[k] = nums[i];
}
return res;
}CareerCup All in One 문제 요약
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
