Τι είναι το μισό ενός πίνακα και πώς το…

Το ήμισυ ενός πίνακα (ή το "μεσαίο" του πίνακα, αν είναι ταξινομημένος) είναι το στοιχείο που, αν ο πίνακας είναι ταξινομημένος, τον διαιρεί σε δύο μέρη: στοιχεία μικρότερα ή ίσα με το μεσαίο και στοιχεία μεγαλύτερα ή ίσα με το μεσαίο. Αν ο αριθμός των στοιχείων είναι ζυγός, το μεσαίο συχνά υπολογίζεται ως ο μέσος όρος των δύο κεντρικών στοιχείων. Στο πλαίσιο του "ημισυ του πίνακα" σε ερωτήσεις συνέντευξης, μπορεί επίσης να αναφέρεται στην αναζήτηση ενός κυρίαρχου στοιχείου, που εμφανίζεται περισσότερες από N/2 φορές, όπου N είναι ο αριθμός των στοιχείων στον πίνακα.

Ο ορισμός του ημισυ του πίνακα εξαρτάται από το πλαίσιο:

Μεσαίο (για ταξινομημένο πίνακα ή κατά την αναζήτηση του k-οστού μικρότερου στοιχείου):
- Ταξινομούμε τον πίνακα.
- Αν το μέγεθος N είναι περιττό, το μεσαίο είναι το στοιχείο στη θέση N/2.
- Αν το μέγεθος N είναι ζυγό, το μεσαίο είναι ο μέσος όρος των στοιχείων στις θέσεις N/2 - 1 και N/2.
Κυρίαρχο στοιχείο (που εμφανίζεται > N/2 φορές):
- Χρησιμοποιούμε τον αλγόριθμο ψηφοφορίας Boyer (Boyer–Moore majority vote algorithm).
- Δημιουργούμε μια μεταβλητή candidate και count.
- Διατρέχουμε τα στοιχεία του πίνακα. Αν το τρέχον στοιχείο είναι ίσο με το candidate, αυξάνουμε το count. Αν όχι, και το count > 0, μειώνουμε το count. Αν το count = 0, το τρέχον στοιχείο γίνεται το νέο candidate, και το count τίθεται σε 1.
- Μετά από μια πρώτη διαδρομή, το candidate είναι ένα πιθανό κυρίαρχο στοιχείο. Για να το επιβεβαιώσουμε, πραγματοποιούμε μια δεύτερη διαδρομή για να διασφαλίσουμε ότι πραγματικά εμφανίζεται περισσότερο από N/2 φορές.

Παράδειγμα καθορισμού μεσαίου (σε Swift):

// Ταξινόμηση για εύρεση μεσαίου
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
    }
}

Παράδειγμα καθορισμού κυρίαρχου στοιχείου (σε Swift):

// Αλγόριθμος ψηφοφορίας Boyer
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
        }
    }

    // Έλεγχος αν ο υποψήφιος είναι πραγματικά κυρίαρχο στοιχείο
    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 // Δεν υπάρχει κυρίαρχο στοιχείο
}

Είναι σημαντικό να διευκρινιστεί με τον συνεντευκτή ποιος ακριβώς τύπος "ημισυ του πίνακα" εννοείται στο πλαίσιο της εργασίας.

Τι είναι το μισό ενός πίνακα και πώς το προσδιορίζουμε;