Untitled

 avatar
unknown
plain_text
a month ago
2.4 kB
2
Indexable
function solution2(expenses) {
    let allExpenses = [];

    // Przechodzimy przez każdy miesiąc
    for (const month in expenses) {
        const days = expenses[month];

        // Przechodzimy przez każdy dzień w miesiącu
        for (const day in days) {
            const categories = days[day];

            // Sprawdzamy, czy dzień jest pierwszą niedzielą lub wcześniejszy
            const date = new Date(`${month}-${day}`);
            if (date.getDay() === 0 || date.getDate() <= 7) {
                // Dodajemy wszystkie wydatki do listy
                for (const category in categories) {
                    allExpenses = allExpenses.concat(categories[category]);
                }
            }
        }
    }

    // Jeśli nie ma wydatków, zwracamy null
    if (allExpenses.length === 0) return null;

    // Używamy szybkiego sortowania do znalezienia mediany
    const quickSelect = (arr, k) => {
        if (arr.length === 1) return arr[0];

        const pivot = arr[Math.floor(Math.random() * arr.length)];
        const lows = arr.filter(x => x < pivot);
        const highs = arr.filter(x => x > pivot);
        const pivots = arr.filter(x => x === pivot);

        if (k < lows.length) {
            return quickSelect(lows, k);
        } else if (k < lows.length + pivots.length) {
            return pivots[0];
        } else {
            return quickSelect(highs, k - lows.length - pivots.length);
        }
    };

    const mid = Math.floor(allExpenses.length / 2);
    if (allExpenses.length % 2 === 0) {
        const left = quickSelect(allExpenses, mid - 1);
        const right = quickSelect(allExpenses, mid);
        return (left + right) / 2;
    } else {
        return quickSelect(allExpenses, mid);
    }
}

// Uzasadnienie:
// W solution2 zastosowano szybkie sortowanie (quick select) do znalezienia mediany.
// Zalety:
// - Szybkie sortowanie ma średnią złożoność czasową O(n), co jest lepsze niż O(n log n) dla standardowego sortowania.
// - Nie wymaga sortowania całej tablicy, co oszczędza pamięć.
// Wady:
// - W najgorszym przypadku złożoność czasowa może wynieść O(n^2), ale jest to mało prawdopodobne przy losowym wyborze pivota.
// - Implementacja jest nieco bardziej skomplikowana niż standardowe sortowanie.
Editor is loading...
Leave a Comment