Massivin yarısı nədir və onu necə müəyyən etmək olar…

Massivın (və ya sıralanmışsa, massivın "medianası") yarısı, massiv sıralanmışsa, onu iki hissəyə bölən elementdir: medianadan kiçik və ya ona bərabər elementlər və medianadan böyük və ya ona bərabər elementlər. Əgər elementlərin sayı cütdürsə, median adətən iki mərkəzi elementin arifmetik orta hesabı kimi hesablanır. İşə qəbul suallarında "massivin yarısı" kontekstində, N/2-dən çox dəfə rast gəlinən ümumi elementi tapmaq da nəzərdə tutula bilər, burada N massivdəki elementlərin sayıdır.

Massivin yarısının tərifi kontekstdən asılıdır:

Median (sıralanmış massiv üçün və ya k-ən kiçik elementin axtarışında):
- Massivi sıralayırıq.
- Əgər N təkdirsə, median N/2 indeksindəki elementdir.
- Əgər N cütdürsə, median N/2 - 1 və N/2 indekslərindəki elementlərin arifmetik ortasıdır.
Ümumi element (N/2-dən çox dəfə rast gəlinən):
- Boyer səsvermə algoritmindən istifadə edirik.
- candidate və count dəyişənləri yaradırıq.
- Massiv elementlərini keçiririk. Əgər cari element candidate-a bərabərdirsə, count-u artırırıq. Əks halda, və count > 0 isə, count-u azaldırıq. Əgər count = 0 isə, cari element yeni candidate olur və count 1-ə bərabər olur.
- Birinci keçiddən sonra, candidate potensial ümumi elementdir. Bunu təsdiqləmək üçün ikinci keçid aparılır və onun həqiqətən N/2-dən çox rast gəlinib-görülmədiyi yoxlanılır.

Swift-də medianın tapılması nümunəsi:

// Sıralama ilə medianı tapmaq
func findMedian(in array: [Int]) -> Double? {
    guard !array.isEmpty else { return nil }

    let sortedArray = array.sorted()
    let n = sortedArray.count

    if n % 2 == 1 {
        return Double(sortedArray[n / 2])
    } else {
        return Double(sortedArray[n / 2 - 1] + sortedArray[n / 2]) / 2.0
    }
}

Ümumi elementi tapmaq nümunəsi (Swift-də):

// Boyer səsvermə algoritmi
func findMajorityElement(in array: [Int]) -> Int? {
    var candidate: Int? = nil
    var count = 0

    for element in array {
        if count == 0 {
            candidate = element
            count = 1
        } else if element == candidate {
            count += 1
        } else {
            count -= 1
        }
    }

    // Kandidatın həqiqətən ümumi element olub-olmadığını yoxlamaq
    var realCount = 0
    if let candidate = candidate {
        for element in array {
            if element == candidate {
                realCount += 1
            }
        }
        if realCount > array.count / 2 {
            return candidate
        }
    }

    return nil // Ümumi element tapılmadı
}

"Massivin yarısı" ifadəsinin kontekstdə hansı dəqiq növü nəzərdə tutulduğunu aydınlaşdırmaq vacibdir.

Massivin yarısı nədir və onu necə müəyyən etmək olar?