Skip to Content
CoursesCSC102การหาสมาชิกร่วมของอาร์เรย์ที่เรียงลำดับแล้ว

การหาสมาชิกร่วมของอาร์เรย์ที่เรียงลำดับแล้ว

โจทย์

Given two sorted arrays in non-decreasing order, print all common elements in these arrays.

Input:

  • The first line of input consists of an integer n, which is the length of the first array.
  • The second line of input consists of n positive integers separated by a space. These are the numbers of the first array.
  • The third line of input consists of an integer m, which is the length of the second array.
  • The fourth line of input consists of m positive integers separated by a space. These are the numbers of the second array.

Output:

  • The program prints all the common elements of the two arrays separated by a space. If there are no common elements print “No common elements”.

Constraints:

  • The input integer (n) must be greater than 0. [n > 0].
  • The input integer (m) must be greater than 0. [m > 0].
InputOutput
4
1 2 3 4
4
1 1 2 2		1 2
3
1 1 1
3
0 0 0		No common elements

โค้ด

import java.util.Scanner;
 
public class Program {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int firstArrayLength = scanner.nextInt();
        int[] firstArray = new int[firstArrayLength];
        for (int i = 0; i < firstArrayLength; i++) {
            firstArray[i] = scanner.nextInt();
        }
 
        int secondArrayLength = scanner.nextInt();
        int[] secondArray = new int[secondArrayLength];
        for (int i = 0; i < secondArrayLength; i++) {
            secondArray[i] = scanner.nextInt();
        }
 
        int found = 0;
        int i = 0, j = 0;
        while (i < firstArrayLength && j < secondArrayLength) {
            if (firstArray[i] == secondArray[j]) {
                System.out.print(firstArray[i] + " ");
                i++;
                found++;
            }
            j++;
        }
 
        if (found == 0) {
            System.out.println("No common elements");
        }
    }
}

คำอธิบาย

1. การรับข้อมูล

// รับข้อมูลอาร์เรย์แรก
int firstArrayLength = scanner.nextInt();
int[] firstArray = new int[firstArrayLength];
for (int i = 0; i < firstArrayLength; i++) {
    firstArray[i] = scanner.nextInt();
}
 
// รับข้อมูลอาร์เรย์ที่สอง
int secondArrayLength = scanner.nextInt();
int[] secondArray = new int[secondArrayLength];
for (int i = 0; i < secondArrayLength; i++) {
    secondArray[i] = scanner.nextInt();
}

2. การหาสมาชิกร่วม

int found = 0;          // นับจำนวนสมาชิกร่วมที่พบ
int i = 0, j = 0;       // ตัวชี้ตำแหน่งในแต่ละอาร์เรย์
 
while (i < firstArrayLength && j < secondArrayLength) {
    if (firstArray[i] == secondArray[j]) {
        System.out.print(firstArray[i] + " ");
        i++;
        found++;
    }
    j++;
}

3. การตรวจสอบและแสดงผล

if (found == 0) {
    System.out.println("No common elements");
}

แผนภาพการทำงาน

ตัวอย่างการทำงาน

กรณี 1: มีสมาชิกร่วม

อาร์เรย์ 1: [1, 2, 4, 5]
อาร์เรย์ 2: [2, 4, 6, 7]
ผลลัพธ์: 2 4

กรณี 2: ไม่มีสมาชิกร่วม

อาร์เรย์ 1: [1, 3, 5]
อาร์เรย์ 2: [2, 4, 6]
ผลลัพธ์: No common elements
ปรับปรุงล่าสุด