資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究隨機挑選 C++ 索引
假設我們有一個可能包含重複元素的整數陣列，我們必須隨機挑選一個給定目標數字的索引。我們可以假設給定的目標數字一定存在於陣列中。因此，如果陣列如下所示：[1,2,3,3,3]，則 pick(3) 可能隨機返回 2、3 或 4。
為了解決這個問題，我們將遵循以下步驟 -
ret := - 1, cnt := 1
對於 i 介於 0 至 v 的大小
如果 v[i] = target，那麼
如果隨機數模 cnt = 0，那麼 ret = i
cnt := cnt + 1
返回 ret
示例 (C++)
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <int> v;
Solution(vector<int>& nums) {
srand(time(NULL));
v = nums;
}
int pick(int target) {
int ret = -1;
int cnt = 1;
for(int i = 0; i < v.size(); i++){
if(v[i] == target){
if(rand() % cnt++ == 0) ret = i;
}
}
return ret;
}
};
main(){
vector<int> v = {1,2,3,3,3};
Solution ob(v);
cout << (ob.pick(3));
}輸入
Initialize with [1,2,3,3,3] Call pick(3) to get random index positions
輸出
4 3 4 2
更新於： 2020 年 5 月 2 日
640 次瀏覽
廣告