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

O（n）で配列内の重複を検索し、C ++でO（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. C++で重複するサブツリーを検索する

    二分木があるとします。重複するすべてのサブツリーを見つける必要があります。したがって、重複するサブツリーの種類ごとに、それらのいずれかのルートノードを返す必要があります。したがって、-のようなツリーがあるとします。 重複するサブツリーは-です これを解決するには、次の手順に従います- 配列retを作成し、マップを作成しますm 再帰メソッドsolve（）を定義します。これはノードを入力として受け取ります。これは次のように機能します- ノードがnullの場合、-1を返します x：=ノードの値を文字列として、「＃」を連結します。 左：=ソルブ（ノードの左）、右：=ソルブ（ノード

  2. C ++を使用して、ソートされていない配列で床と天井を検索します。

    ここでは、並べ替えられていない配列で床と天井を見つける方法を説明します。床の値はx以下の大きい要素であり、天井の値はxより大きい最小値です。配列A=[5、6、8、9、6、5、5、6]で、xが7の場合、フロア値は6、シーリング値は8です。 この問題を解決するために、線形探索アプローチに従います。配列をトラバースし、xに関して2つの距離を追跡します。 x以上の要素の最小距離 x以下の要素の最小距離 最後に、最小距離の印刷要素 例 #include<iostream> using namespace std; void floorCeilingPair(int arr[], int