C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++でのランダムピックインデックス

重複の可能性がある整数の配列があるとすると、指定されたターゲット番号のインデックスをランダムに選択する必要があります。指定されたターゲット番号が配列に存在する必要があると想定できます。したがって、配列が[1,2,3,3,3]のような場合、pick（3）は2、3、4をランダムに返す可能性があります。

これを解決するには、次の手順に従います-

  • ret：=-1、cnt：=1

  • 0からvのサイズまでの範囲のiの場合

    • v [i] =ターゲットの場合、

      • 乱数modcnt=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

  1. C++で右側にあるNGEの数

    ターゲット要素の配列とインデックスが与えられます。右側の指定された要素よりも大きい要素の数を数える必要があります。例を見てみましょう。 入力 arr = [2, 3, 5, 1, 4, 2, 6] index = 3 出力 3 ターゲットインデックス要素は1です。右側に1より大きい3つの要素、つまり...、4、2、6があります。 アルゴリズム ターゲット要素の配列とインデックスを初期化します。 インデックスが配列の長さ以上の場合は、-1を返します。 指定されたインデックスの次の要素から繰り返すループを記述します。 要素がターゲット要素よりも大きい場合は、カウントを増やします。

  2. C++でランダムポインタを使用してリストをコピーする

    リンクリストは線形データ構造であり、各ノードには2つのブロックがあり、一方のブロックにはノードの値またはデータが含まれ、もう一方のブロックには次のフィールドのアドレスが含まれます。 各ノードにリスト内の他のノードを指すランダムポインタが含まれるようなリンクリストがあると仮定します。タスクは、元のリストと同じリストを作成することです。ランダムなポインタを持つ元のリストからリストをコピーすることを、リンクリストの「ディープコピー」と呼びます。 例 入力-1 出力： 5-> 2 -> 3 -> 7 ->4 -> 説明： この問題を解決するためのア