หา Equal Point (จุดที่จำนวนน้อยกว่าเท่ากับจำนวนมากกว่า) ในอาร์เรย์เรียงลำดับมีค่าซ้ำ (C++)

ให้อาร์เรย์เรียงลำดับมี n องค์ประกอบ หา Index ที่จำนวนสมาชิกน้อยกว่าค่าที่ Index นั้น เท่ากับจำนวนสมาชิกมากกว่า หากมีหลาย Index ให้คืน Index แรก หากไม่มีคืน -1

ตัวอย่าง: A = [1, 1, 2, 3, 3, 3, 3, 3] → Equal Point อยู่ที่ Index 2 (ค่า 2) เพราะมีค่าน้อยกว่า 1 ค่า (1) และค่ามากกว่า 1 ค่า (3)

อัลกอริทึม

1. สร้างอาร์เรย์ช่วย (aux_arr) เก็บ Index ของค่าที่ไม่ซ้ำ (Distinct elements)
2. ถ้าจำนวนค่าที่ไม่ซ้ำเป็นเลขคู่ → ไม่มี Equal Point
3. ถ้าเป็นเลขคี่ → Equal Point คือค่ากลางของ Distinct elements

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int searchEqualPoint(int arr[], int n) {
    int aux_arr[n];
    int i = 0, aux_index = 0;

    while (i < n) {
        aux_arr[aux_index++] = i++;
        while (i < n && arr[i] == arr[i-1])
            i++;
    }

    // aux_index & 1 ตรวจสอบเลขคี่, aux_index >> 1 คือหาร 2 (index กลาง)
    return (aux_index & 1) ? aux_arr[aux_index >> 1] : -1;
}

int main() {
    int arr[] = {1, 1, 2, 3, 3, 3, 3, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = searchEqualPoint(arr, n);

    if (index != -1)
        cout << "Equal Point is: " << arr[index];
    else
        cout << "No Equal Point exists";

    return 0;
}

ผลลัพธ์

Equal Point is: 2

ความซับซ้อน

เวลา: O(n), พื้นที่: O(n) สำหรับอาร์เรย์ช่วย