Đếm số lần xuất hiện của phần tử lặp duy nhất trong mảng liên tiếp đã sắp xếp C++

Cho mảng đã sắp xếp chứa các số nguyên liên tiếp, có đúng một số bị lặp lại nhiều lần. Mục tiêu tìm số lần xuất hiện của phần tử đó.

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {0, 1, 2, 3, 3, 3}, N = 6
• Output: 3
• Giải thích: Số 3 xuất hiện 3 lần.

Ví dụ 2:

• Input: arr = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6}, N = 10
• Output: 5
• Giải thích: Số 4 xuất hiện 5 lần.

Thuật toán

Vì mảng đã sắp xếp và các số liên tiếp, phần tử lặp sẽ nằm liền nhau. Duyệt mảng, đếm số cặp arr[i] == arr[i+1], rồi cộng 1 cho phần tử cuối cùng của dãy lặp.

Mã nguồn C++

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

void findRepeat(int arr[], int n) {
    int count = 0;
    int value = 0;
    for (int i = 0; i < n - 1; i++) {  // Sửa: i < n-1 để tránh truy cập arr[n]
        if (arr[i] == arr[i + 1]) {
            count++;
            value = arr[i];
        }
    }
    count++; // Cộng cho phần tử cuối cùng của dãy lặp
    cout << "Phan tu lap: " << value;
    cout << endl << "So lan xuat hien: " << count;
}

int main() {
    int Arr[] = {2, 3, 4, 5, 5, 5, 6, 7, 8};
    int len = sizeof(Arr) / sizeof(Arr[0]);
    findRepeat(Arr, len);
    return 0;
}

Kết quả chạy chương trình

Phan tu lap: 5
So lan xuat hien: 3

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(1)

Tối ưu O(log n) bằng Binary Search

Vì mảng đã sắp xếp, có thể dùng binary search tìm vị trí đầu và cuối của phần tử lặp:

int findRepeatCount(int arr[], int n) {
    // Tìm phần tử lặp (arr[i] == arr[i+1])
    int left = 0, right = n - 2, repeatVal = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == arr[mid + 1]) {
            repeatVal = arr[mid];
            break;
        } else if (arr[mid] > mid + arr[0]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (repeatVal == -1) return 0;
    
    // Tìm vị trí đầu và cuối
    int first = lower_bound(arr, arr + n, repeatVal) - arr;
    int last = upper_bound(arr, arr + n, repeatVal) - arr - 1;
    return last - first + 1;
}