C++で積が指定した値に等しくなる2つの連結リストのペアを数える方法

2つの連結リストが与えられ、それぞれのリストが持つ整数要素を組み合わせて、その積が指定された値(k)と等しくなるペアがいくつ存在するかを求めるのが課題です。連結リスト(リンクリスト)とは、リンク(ポインタ)によって順々に接続されたデータ構造の列のことを指します。

入力例と出力例

例1

入力:

vector v_1 = {5, 7, 8, 10, 11}
vector v_2 = {6, 4, 3, 2, 0}
int k = 20

出力:

積が指定された値kに等しい2つの連結リストのペアの数: 2

説明:

2つの連結リストから作成できるペアは全部で 5 × 5 = 25通りあります。そのうち積が20と等しくなるのは、(5, 4) = 20 と (10, 2) = 20 の2通りだけです。したがって、条件を満たすペアの数は2となります。

例2

入力:

vector v_1 = {2, 3, 5, 6}
vector v_2 = {6, 4, 3}
int k = 9

出力:

積が指定された値kに等しい2つの連結リストのペアの数: 1

説明:

作成できるペアは全部で 4 × 3 = 12通りあります。そのうち積が9と等しくなるのは (3, 3) = 9 の1通りだけです。したがって、条件を満たすペアの数は1となります。

プログラムで使用するアプローチ

• kの値と整数型の値を2つのvectorに入力し、これらのベクトルから連結リストを構築できるようにします。

• 引数として渡されたvectorをもとに連結リストを作成する関数を作成します。

  • vectorのサイズ分だけループを回し、ListNodeクラスのポインタオブジェクトを作成します。

  • ptr->nextがNULLでなくなる間、ptrをptr->nextに進めてリストの末尾を探します。

  • 末尾のptr->nextに新しいListNode(vector[i])を接続します。

  • 先頭ポインタstartを返します。

• 指定された積に一致するペアの個数を返す関数を作成します。

  • 一時変数countを宣言し、0で初期化します。

  • 2つのポインタオブジェクト、すなわち1つ目の連結リスト用の*first_listと、2つ目の連結リスト用の*second_listを用意します。

  • 1つ目のリストの先頭ポインタから、リストが空になるまで外側のループを実行します。

  • そのループ内で、2つ目のリストの先頭ポインタから、リストが空になるまで内側のループを実行します。

  • ループ内で (first_list->data * second_list->data) == k が成り立つかどうかを判定し、成り立てばcountを1増やします。

  • countを返します。

• 結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int data;
    ListNode *next;
    ListNode(int data) {
        this->data = data;
        next = NULL;
    }
};

ListNode *CreateList(vector<int> v) {
    ListNode *start = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode *ptr = start;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return start;
}

int product_pair(ListNode *start_1, ListNode *start_2, int k) {
    int count = 0;
    ListNode *first_list, *second_list;
    for (first_list = start_1; first_list != NULL; first_list = first_list->next) {
        for (second_list = start_2; second_list != NULL; second_list = second_list->next) {
            if ((first_list->data * second_list->data) == k) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> v_1 = {5, 7, 8, 10, 11};
    ListNode* start_1 = CreateList(v_1);
    vector<int> v_2 = {6, 4, 3, 2, 0};
    ListNode* start_2 = CreateList(v_2);
    int k = 30;
    cout << "積が指定された値kに等しい2つの連結リストのペアの数: " << product_pair(start_1, start_2, k);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

積が指定された値kに等しい2つの連結リストのペアの数: 2

計算量

このアプローチでは、1つ目のリストの各要素に対して2つ目のリストの全要素を順に調べるため、時間計算量はO(N×M)(N・Mはそれぞれのリストの長さ)となります。一方、追加のデータ構造を使用しないため、空間計算量はO(1)です。