Untitled
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