a%b = kとなるような配列内のすべてのペア(a、b)を見つけます


難易度 ハード
よく聞かれる Amazon (アマゾン) アルセシウム 要塞 ディレクティ 費用無料 Yahoo
配列 ハッシュ モジュラー演算

問題文

「%b = kとなるような配列内のすべてのペア(a、b)を検索する」という問題は、整数の配列と次の整数値が与えられていることを示しています。 k。 問題ステートメントは、配列内でx%y = k(指定された値)となるような方法でペアを見つけるように要求します。

arr[] = {3, 4, 7, 5, 6 }
k = 3
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

説明

これらの4つのペアは、%b = kが真の場合に確認されています。

a%b = kとなるような配列内のすべてのペア(a、b)を見つけます

arr[]={2, 3, 5, 1},
k = 2
(2, 3) (2, 5) (5, 3)

説明

これらの3つのペアは、%b = kが真の場合に確認されています。

アルゴリズム

  1. 宣言する 地図 そして、その引数のXNUMXつをとして選択します ブーリアン.
  2. オリジナルをトラバースする 配列 真のブール値を持つ配列のすべての値をマップに格納します。
  3. ブール変数を次のように設定します ペアチェック falseに。
  4. 配列を0からn-1までトラバースします(nは配列の長さです)。
    1. 指定されたk値にマップ内のエントリがあり、kが現在の配列要素よりも小さいかどうかを確認します。 trueの場合、値kとその配列要素を出力し、そのブール値をtrueに設定します。
    2. kが現在の配列要素以下であるかどうかを確認します。
      1. trueの場合、ベクトルを作成し、arr [i] -k値のすべての除数を見つけて、それをベクトルに格納します。
      2. そのベクトルをトラバースし、ベクトルのその要素と配列要素が、モジュロが実行されたときの条件を満たすペアであるかどうかを確認します。
        1. ベクトルと現在の配列要素を出力し、ブール値をtrueに設定します。
  5. 返品 ペアチェック.

説明

整数の配列と整数値kが与えられます。 x%y = kとなるようなペア(x、y)のモジュロ演算を実行するときに、そのペアを出力する必要があるようにペアを見つけます。これは、整数配列全体で行う必要があります。 数値x%yに対してモジュロ演算を実行するときに、値kを与えるすべてのペアを見つけます。 このために、vector andmapと呼ばれるコレクションまたはSTLのXNUMXつを使用します。

すべての配列要素をマップに配置し、それらすべてに「真の」ブール値をマークします。 と呼ばれるブール変数を初期化する必要があります ペアチェック 偽に。 正しいペアが見つかったら更新します。 次に、配列をトラバースします。 そして、与えられたk値がマップに存在するかどうかを確認します。 また、kが現在の配列要素よりも小さい場合。 次に、そのペアを印刷します。 小さい数を大きい数で割ると、余りが小さい数になるからです。

上記の条件が偽になった場合、現在の要素がkより大きいかどうかを確認します。 trueの場合、現在の配列要素とkの差を渡すベクトルを宣言する必要があります。これにより、可能な値のペアが返されるベクトルが返されます。 それぞれの値を選択し、ベクトルの戻り値を法とする現在の配列要素が剰余kを与えるかどうかを確認します。 trueの場合、ペアを出力し、pairCheck値をtrueとしてマークします。これは、少なくともXNUMXつのペアが見つかったことを意味します。 同じ手順でさらに価値を高め、考えられるすべての結果を印刷します。

コード

a%b = kとなるような配列内のすべてのペア(a、b)を検索するためのC ++での実装

#include <unordered_map>
#include<vector>
#include<iostream>
#include<math.h>

using namespace std;

vector<int> findPossibleDiv(int n)
{
    vector<int> vecDiv;

    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            if (n / i == i)
                vecDiv.push_back(i);
            else
            {
                vecDiv.push_back(i);
                vecDiv.push_back(n / i);
            }
        }
    }
    return vecDiv;
}
bool pairModulousK(int arr[], int n, int k)
{
    unordered_map<int, bool> MAP;
    for (int i = 0; i < n; i++)
        MAP[arr[i]] = true;

    bool pairCheck = false;
    for (int i = 0; i < n; i++)
    {
        if (MAP[k] && k < arr[i])
        {
            cout << "(" << k << ", " << arr[i] << ") ";
            pairCheck = true;
        }
        if (arr[i] >= k)
        {
            vector<int> vec = findPossibleDiv(arr[i] - k);

            for (int j = 0; j < vec.size(); j++)
            {
                if (arr[i] % vec[j] == k && arr[i] != vec[j] && MAP[vec[j]])
                {
                    cout << "(" << arr[i] << ", "<< vec[j] << ") ";
                    pairCheck = true;
                }
            }
            vec.clear();
        }
    }
    return pairCheck;
}
int main()
{
    int arr[] = { 3, 4, 7, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    if (pairModulousK(arr, n, k) == false)
        cout << "No such pair exists";
    return 0;
}
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

a%b = kとなるような配列内のすべてのペア(a、b)を検索するJavaコード

import java.util.HashMap;
import java.util.Vector;

class PairModuloK
{
    public static Vector<Integer> findPossibleDiv(int n)
    {
        Vector<Integer> vecDiv = new Vector<>();

        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0)
            {
                if (n / i == i)
                    vecDiv.add(i);
                else
                {
                    vecDiv.add(i);
                    vecDiv.add(n / i);
                }
            }
        }
        return vecDiv;
    }
    public static boolean pairModulousK(int arr[], int n, int k)
    {
        HashMap<Integer, Boolean> MAP = new HashMap<>();
        for (int i = 0; i < n; i++)
            MAP.put(arr[i], true);

        boolean pairCheck = false;
        for (int i = 0; i < n; i++)
        {
            if (MAP.get(k) && k < arr[i])
            {
                System.out.print("(" + k + ", " + arr[i] + ") ");
                pairCheck = true;
            }
            if (arr[i] >= k)
            {
                Vector<Integer> vec = findPossibleDiv(arr[i] - k);

                for (int j = 0; j < vec.size(); j++)
                {
                    if (arr[i] % vec.get(j) == k && arr[i] != vec.get(j) && MAP.get(vec.get(j)))
                    {
                        System.out.print("(" + arr[i] + ", "
                                         + vec.get(j) + ") ");
                        pairCheck = true;
                    }
                }
                vec.clear();
            }
        }

        return pairCheck;
    }
    public static void main(String args[])
    {
        int arr[] = {3, 4, 7, 6, 5};
        int k = 3;

        if (pairModulousK(arr, arr.length, k) == false)
            System.out.println("No such pair exists");
    }
}
(3, 4) (3, 7) (7, 4) (3, 6) (3, 5)

複雑さの分析

時間の複雑さ

O(n * sqrt(max)) where 「最大」 配列内の最大要素です。 今回は、使用したために複雑さが達成されました

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 このスペースは、マップに要素を格納するために必要です。