ค้นหาคู่ทั้งหมด (a, b) ในอาร์เรย์เพื่อให้ a% b = k


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน อาร์ซีเซียม ป้อมปราการ Directi ฟรีค่าธรรมเนียม yahoo
แถว กัญชา เลขคณิตโมดูลาร์

คำชี้แจงปัญหา

ปัญหา“ ค้นหาคู่ทั้งหมด (a, b) ในอาร์เรย์เพื่อให้% b = k” ระบุว่าคุณได้รับอาร์เรย์ของจำนวนเต็มและค่าจำนวนเต็มที่เรียกว่า 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) ในอาร์เรย์เพื่อให้ a% b = k

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

คำอธิบาย

3 คู่นี้ได้รับการยืนยันแล้วเมื่อ% b = k เป็นจริง

ขั้นตอนวิธี

  1. ประกาศก แผนที่ และเลือกหนึ่งในอาร์กิวเมนต์เป็น บูลีน.
  2. สำรวจต้นฉบับ แถว และเก็บค่าทั้งหมดของอาร์เรย์ด้วยค่าบูลีนที่แท้จริงลงในแผนที่
  3. ตั้งค่าตัวแปรบูลีนที่จะพูด คู่ตรวจสอบ เป็นเท็จ
  4. สำรวจอาร์เรย์จาก 0 ถึง n-1 (n คือความยาวของอาร์เรย์)
    1. ตรวจสอบว่าค่า k ที่ระบุมีรายการในแผนที่หรือไม่และ k มีขนาดเล็กกว่าองค์ประกอบอาร์เรย์ปัจจุบันหรือไม่ ถ้าเป็นจริงให้พิมพ์ค่า k และองค์ประกอบอาร์เรย์นั้นและตั้งค่าบูลีนเป็นจริง
    2. ตรวจสอบว่า k น้อยกว่าหรือเท่ากับองค์ประกอบอาร์เรย์ปัจจุบันหรือไม่
      1. ถ้าเป็นจริงให้สร้างเวกเตอร์และค้นหาตัวหารทั้งหมดของค่า arr [i] -k และเก็บไว้ในเวกเตอร์
      2. สำรวจเวกเตอร์นั้นและตรวจสอบว่าองค์ประกอบของเวกเตอร์และองค์ประกอบอาร์เรย์นั้นเป็นคู่ที่ตรงตามเงื่อนไขเมื่อโมดูโลเสร็จสิ้นหรือไม่
        1. พิมพ์เวกเตอร์และองค์ประกอบอาร์เรย์ปัจจุบันและตั้งค่าบูลีนเป็นจริง
  5. การส่งคืนสินค้า คู่ตรวจสอบ.

คำอธิบาย

กำหนดอาร์เรย์ของจำนวนเต็มและค่าจำนวนเต็ม k ค้นหาคู่ในลักษณะที่เมื่อเราดำเนินการโมดูโลกับคู่ (x, y) เช่นนั้น x% y = k จากนั้นเราต้องพิมพ์คู่นั้นเราต้องทำสิ่งนี้กับอาร์เรย์จำนวนเต็มทั้งหมด ค้นหาคู่ทั้งหมดที่ให้ค่า k เมื่อเราดำเนินการโมดูโลกับตัวเลข x% y สำหรับสิ่งนี้เราจะใช้หนึ่งในคอลเลกชันหรือ STL ที่เรียกว่าเวกเตอร์และแผนที่

ใส่องค์ประกอบอาร์เรย์ทั้งหมดลงในแผนที่และทำเครื่องหมายทั้งหมดด้วยค่าบูลีน "จริง" เราจำเป็นต้องเริ่มต้นตัวแปรบูลีนที่เรียกว่า คู่ตรวจสอบ เป็นเท็จ เราจะอัปเดตเมื่อพบคู่ที่ถูกต้อง จากนั้นเราจะสำรวจอาร์เรย์ตอนนี้ และตรวจสอบว่าค่า k ที่ระบุมีอยู่ในแผนที่หรือไม่ นอกจากนี้ถ้า k น้อยกว่าองค์ประกอบอาร์เรย์ปัจจุบัน จากนั้นเราก็พิมพ์คู่นั้น เพราะเมื่อเราหารจำนวนน้อยด้วยจำนวนที่มากขึ้นมันจะทำให้ส่วนที่เหลือเป็นจำนวนน้อย

หากเงื่อนไขข้างต้นกลายเป็นเท็จเราจะตรวจสอบว่าองค์ประกอบปัจจุบันมีค่ามากกว่า k หรือไม่ ถ้าเป็นจริงเราจำเป็นต้องประกาศเวกเตอร์ที่เราส่งผ่านความแตกต่างขององค์ประกอบอาร์เรย์ปัจจุบันและ k ซึ่งจะส่งคืนเวกเตอร์ที่คู่ค่าที่เป็นไปได้จะถูกส่งกลับ เราจะเลือกแต่ละค่าและตรวจสอบว่าโมดูโลองค์ประกอบอาร์เรย์ปัจจุบันส่งคืนค่าในเวกเตอร์ให้ค่า k ที่เหลือหรือไม่ หากเป็นจริงให้พิมพ์คู่และทำเครื่องหมายที่ค่า pairCheck ว่าเป็นจริงซึ่งหมายความว่าเราพบอย่างน้อยหนึ่งคู่ ดำเนินการตามค่าเพิ่มเติมด้วยขั้นตอนเดียวกันและพิมพ์ผลลัพธ์ที่เป็นไปได้ทั้งหมด

รหัส

การนำไปใช้งานใน C ++ เพื่อค้นหาคู่ทั้งหมด (a, b) ในอาร์เรย์เพื่อให้ a% b = k

#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)

รหัส Java เพื่อค้นหาคู่ทั้งหมด (a, b) ในอาร์เรย์เช่น% b = k

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 (สูงสุด)) ที่ไหน “ สูงสุด” เป็นองค์ประกอบสูงสุดในอาร์เรย์ ความซับซ้อนในครั้งนี้เกิดขึ้นได้เพราะเราใช้

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ พื้นที่นี้จำเป็นสำหรับการจัดเก็บองค์ประกอบในแผนที่