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

O（n）時間とO（1）余分なスペースで重複を検索-C++で1を設定

0からn-1までの数字のリストがあるとします。数は可能な限り何度でも繰り返すことができます。余分なスペースをとらずに繰り返し番号を見つける必要があります。 n =7の値で、リストが[5、2、3、5、1、6、2、3、4、5]のような場合。答えは5、2、3になります。

これを解決するには、次の手順に従う必要があります-

リスト内の要素eごとに、次の手順を実行します-

  • sign：=A[eの絶対値]
  • 符号が正の場合は負にします
  • それ以外の場合は繰り返しです。

例

#include<iostream>
#include<cmath>
using namespace std;
void findDuplicates(int arr[], int size) {
   for (int i = 0; i < size; i++) {
      if (arr[abs(arr[i])] >= 0)
         arr[abs(arr[i])] *= -1;
      else
         cout << abs(arr[i]) << " ";
   }
}
int main() {
   int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   findDuplicates(arr, n);
}

出力

5 2 3 1

  1. PythonでO（n）時間とO（1）空間でBSTの中央値を見つける

    二分探索木（BST）があるとすると、その中央値を見つける必要があります。偶数のノードの場合、中央値=（（n / 2番目のノード+（n + 1）/ 2番目のノード）/ 2奇数のノードの場合、中央値=（n + 1）/2番目のノードです。 したがって、入力が次のような場合 その場合、出力は7になります これを解決するには、次の手順に従います- rootがNoneと同じ場合、 0を返す node_count：=ツリー内のノードの数 count_curr：=0 現在：=ルート currentがnullでない場合は、実行してください curren

  2. PythonでO（n）時間とO（1）余分なスペースで最大繰り返し数を見つけます

    配列内の要素が0からk-1の範囲にある場合、サイズnの配列があるとします。ここで、kは正の整数として表され、k<=nです。この配列で最大繰り返し数を見つける必要があります。 したがって、入力がk=8およびA=[3、4、4、6、4、5、2、8]の場合、出力は4になります。 これを解決するには、次の手順に従います- n：=Aのサイズ 0からnの範囲のiの場合、実行 A [A [i] mod k]：=A [A [i] mod k] + k max_val：=A [0] 結果：=0 1からnの範囲のiの場合、実行します max_valの場合、