Массивдеги бардык жуптарды (a, b)% b = k деп табыңыз  


Кыйынчылык деңгээли катуу
Көп суралган Amazon Арцезий Citadel Directi FreeCharge 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)% b = k деп табыңызтөөнөч

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

түшүндүрүү

Бул 3 жуп% b = k чын болгондо тастыкталды.

Algorithm  

  1. Декларация a карта жана анын аргументтеринин бирин а катары тандаңыз Буль.
  2. Түпнускадан өтүңүз согуштук тизме жана массивдин бардык маанилерин чыныгы Буле мааниси бар картага сактаңыз.
  3. Айтууга каалаган логикалык өзгөрмөнү коюңуз pairCheck жалган.
  4. Массивди 0 ден n-1 ге чейин өтүңүз (n - массивдин узундугу).
    1. Берилген k маанисинин картада жазуусу бар экендигин жана ошондой эле k учурдагы массив элементинен кичине экендигин текшериңиз. Эгер чын болсо, анда k маанисин жана ошондой эле массив элементин басып чыгарып, логикалык маанини true деп кой.
    2. K учурдагы массив элементинен кичине же барабар экендигин текшериңиз.
      1. Эгер чын болсо, анда векторду түзүп, arr [i] -k маанисинин бардык бөлүүчүлөрүн таап, аны вектордо сактаңыз.
      2. Ошол векторду айланып өтүп, вектордун жана массивдин элементинин жуп экендигин текшериңиз, ал модуль бүткөндө шартты канааттандырат.
        1. Векторду жана учурдагы массивдин элементин басып чыгарып, логикалык маанидеги маанини чыныгы деп кой.
  5. Return pairCheck.
ошондой эле
Эң кичинекей элемент так K Times кайталанган

түшүндүрүү  

Бүтүн сандардын массиви жана k бүтүн мааниси берилген. Жупту ушундай жол менен тапкыла (x, y) жупка x% y = k деген модулдук операция аткарганда, ошол жупту басып чыгаруу керек, муну бүтүн бүтүн массив менен жасаш керек. X% y санына модулдук амал аткарганда k маанисин берген жуптардын бардыгын табыңыз. Бул үчүн вектор жана карта деп аталган коллекциялардын бирин же STLди колдонобуз.

Массивдин бардык элементтерин картага киргизип, алардын бардыгын "чыныгы" логикалык маани менен белгилеңиз. Логикалык өзгөрмө инициализациясы керек pairCheck жалган. Туура жупту тапканда аны жаңыртууга аракет кылабыз. анда биз азыр массивди аралайбыз. Жана берилген k маани картада бар же жок экендигин текшериңиз. Ошондой эле k учурдагы массив элементинен аз болсо. Андан кийин биз ошол жупту гана басып чыгарабыз. Себеби кичинекей сандарды чоңураак сандарга бөлгөндө, калгандары аз санда калат.

Эгерде жогорудагы шарт жалган болуп калса, анда учурдагы элементтин k ден чоң экендигин текшеребиз. Эгер чын болсо, анда векторду жарыялашыбыз керек, анда учурдагы массив элементинин айырмачылыгы жана k, ал мүмкүн болгон жуптар жуптары кайтарылган векторду кайтарат. Биз ар бир маанини тандап, вектордогу массив элементинин модулу кайтарылган маани калдыкты k бергендигин же бербегендигин текшеребиз. Эгер ал чын болсо, анда жупту басып чыгарып, pairCheck маанисин чыныгы деп белгилеңиз, демек, биз жок дегенде бир жуп таптык. Ушул эле кадамдар менен кошумча нарк менен жүрүп, мүмкүн болгон бардык натыйжаларды басып чыгарыңыз.

ошондой эле
Экинчи Эң көп кайталанган Сөз

коду  

Массивдеги бардык жуптарды (a, b)% b = k деп табуу үчүн 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)% b = k кылып табуу үчүн 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)) кайда "Max" массивдеги эң чоң элемент. Бул убакыттын татаалдыгына биз колдонгонубуз үчүн жетиштик

ошондой эле
Массивди кыскарган формага которуу

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Бул боштук элементтерди картада сактоо үчүн талап кылынат.