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.

Kaedah

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.

Contoh

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));

Arahan

Fungsi

• findMedian menerima matriks sebagai parameter. Ia mula-mula mengira jumlah bilangan elemen dan indeks tengah (median) dalam matriks menggunakan totalElements dan middleIndex masing-masing.

Pembolehubah

• 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!