Rumah > Artikel > hujung hadapan web > Program JavaScript untuk mencari median dalam matriks diisih baris
Kami akan menerangkan proses mencari median dalam matriks diisih baris menggunakan JavaScript. Mula-mula, kita akan mengulangi matriks untuk mengumpul semua elemen ke dalam tatasusunan. Kami kemudian mengisih tatasusunan untuk mencari nilai tengah, yang akan menjadi median kami. Jika terdapat bilangan elemen genap, median ialah purata dua nilai tengah.
Diberikan matriks mengikut baris, median boleh didapati dengan -
Gabungkan semua baris ke dalam tatasusunan yang diisih.
Cari elemen tengah tatasusunan gabungan, ini akan menjadi median.
Jika bilangan elemen dalam tatasusunan gabungan adalah ganjil, kembalikan elemen tengah sebagai median.
Jika bilangan elemen dalam tatasusunan gabungan ialah nombor genap, purata dua elemen tengah dikembalikan sebagai median.
Kerumitan masa kaedah ini ialah O(m * n log (m * n)), dengan m ialah bilangan baris dalam matriks dan n ialah bilangan lajur dalam matriks.
李>Kerumitan ruang ialah O(m * n) kerana keseluruhan matriks perlu digabungkan menjadi tatasusunan.
Berikut ialah contoh lengkap fungsi JavaScript untuk mencari median dalam matriks diisih baris -
function findMedian(matrix) { // Get the total number of elements in the matrix const totalElements = matrix.length * matrix[0].length; // Calculate the middle index of the matrix const middleIndex = Math.floor(totalElements / 2); // Initialize start and end variables to keep track of the search space let start = matrix[0][0]; let end = matrix[matrix.length - 1][matrix[0].length - 1]; while (start <= end) { // Calculate the mid point let mid = Math.floor((start + end) / 2); // Initialize a counter to keep track of the number of elements less than or equal to the mid value let count = 0; // Initialize a variable to store the row index of the last element less than or equal to the mid value let rowIndex = -1; // Loop through each row in the matrix for (let i = 0; i < matrix.length; i++) { // Use binary search to find the first element greater than the mid value in the current row let columnIndex = binarySearch(matrix[i], mid); // If the current row has no element greater than the mid value, increment the count by the length of the row if (columnIndex === -1) { count += matrix[i].length; rowIndex = i; } else { // Otherwise, increment the count by the column index of the first element greater than the mid value count += columnIndex; break; } } // Check if the count of elements less than or equal to the mid value is greater than or equal to the middle index if (count >= middleIndex) { end = mid - 1; } else { start = mid + 1; rowIndex++; } // Check if we have reached the middle index if (count === middleIndex) { return matrix[rowIndex][middleIndex - count]; } } return start; } // Helper function for binary search function binarySearch(arr, target) { let start = 0; let end = arr.length - 1; while (start <= end) { let mid = Math.floor((start + end) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { start = mid + 1; } else { end = mid - 1; } } return start === 0 ? -1 : start - 1; } const arr = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; console.log(findMedian(arr));
findMedian menerima matriks sebagai parameter. Ia mula-mula mengira jumlah bilangan elemen dan indeks tengah (median) dalam matriks menggunakan totalElements dan middleIndex masing-masing.
mula dan akhir masing-masing dimulakan kepada elemen pertama dan terakhir matriks, kerana ia adalah nilai minimum dan maksimum dalam matriks.
Atas ialah kandungan terperinci Program JavaScript untuk mencari median dalam matriks diisih baris. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!