在按行排序的矩阵中求中值-yiteyi-C++库

我们得到一个大小为r*c的按行排序矩阵，我们需要找到给定矩阵的中值。假设r*c总是奇数。 例如：

null

Input : 1 3 5        2 6 9        3 6 9Output : Median is 5If we put all the values in a sorted array A[] = 1 2 3 3 5 6 6 9 9)Input: 1 3 4       2 5 6       7 8 9Output: Median is 5

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

简单方法 ：解决这个问题的最简单方法是将给定矩阵的所有元素存储在大小为r*c的数组中。然后我们可以对数组进行排序，并在O（r*clog（r*c））中找到中值元素，或者我们可以使用讨论的方法在这里求O（r*c）中的中值。两种情况下所需的辅助空间均为O（r*c）。一 有效的方法 对于这个问题，使用二进制搜索算法。这个想法是，对于一个要成为中值的数字，应该有正好（n/2）个小于这个数字的数字。所以，我们试图找到比所有数字都少的数字。下面是这种方法的逐步算法：算法 :

首先，我们找到矩阵中的最小和最大元素。通过比较每行的第一个元素可以很容易地找到最小元素，同样，通过比较每行的最后一个元素可以找到最大元素。
然后我们对从最小值到最大值的数字范围进行二进制搜索，找到最小值和最大值的中间值，得到一个小于或等于中间值的数字，并相应地改变最小值或最大值。
对于一个要成为中值的数字，应该有（r*c）/2个比该数字小的数字。因此，对于每一个数字，我们通过在矩阵的每一行中使用上界（）来得到小于该数字的计数，如果它小于所需计数，则中值必须大于所选数字，否则中值必须小于或等于所选数字。

以下是上述方法的实施情况：

C++

                         // C++ program to find median of a matrix                       
                         // sorted row wise                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         const                                     int                                     MAX = 100;                       
           
                         // function to find median in the matrix                       
                         int                                     binaryMedian(                                     int                                     m[][MAX],                                     int                                     r ,                                     int                                     c)                       
                         {                       
                                                 int                                     min = INT_MAX, max = INT_MIN;                       
                                                 for                                     (                                     int                                     i=0; i<r; i++)                       
                                                 {                       
                                                 // Finding the minimum element                       
                                                 if                                     (m[i][0] < min)                       
                                                 min = m[i][0];                       
           
                                                 // Finding the maximum element                       
                                                 if                                     (m[i][c-1] > max)                       
                                                 max = m[i][c-1];                       
                                                 }                       
           
                                                 int                                     desired = (r * c + 1) / 2;                       
                                                 while                                     (min < max)                       
                                                 {                       
                                                 int                                     mid = min + (max - min) / 2;                       
                                                 int                                     place = 0;                       
           
                                                 // Find count of elements smaller than mid                       
                                                 for                                     (                                     int                                     i = 0; i < r; ++i)                       
                                                 place += upper_bound(m[i], m[i]+c, mid) - m[i];                       
                                                 if                                     (place < desired)                       
                                                 min = mid + 1;                       
                                                 else                       
                                                 max = mid;                       
                                                 }                       
                                                 return                                     min;                       
                         }                       
           
                         // driver program to check above functions                       
                         int                                     main()                       
                         {                       
                                                 int                                     r = 3, c = 3;                       
                                                 int                                     m[][MAX]= { {1,3,5}, {2,6,9}, {3,6,9} };                       
                                                 cout <<                                     "Median is "                                     << binaryMedian(m, r, c) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find median of a matrix                       
                         // sorted row wise                       
                         import                                     java.util.Arrays;                       
           
                         public                                     class                                     MedianInRowSorted                       
                         {                       
                                                 // function to find median in the matrix                       
                                                 static                                     int                                     binaryMedian(                                     int                                     m[][],                                     int                                     r,                                     int                                     c)                       
                                                 {                       
                                                 int                                     max = Integer.MIN_VALUE;                       
                                                 int                                     min = Integer.MAX_VALUE;                       
                                   
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<r ; i++)                       
                                                 {                       
                                   
                                                 // Finding the minimum element                       
                                                 if                                     (m[i][                                     0                                     ] < min)                       
                                                 min = m[i][                                     0                                     ];                       
                                   
                                                 // Finding the maximum element                       
                                                 if                                     (m[i][c-                                     1                                     ] > max)                       
                                                 max = m[i][c-                                     1                                     ];                       
                                                 }                       
                                   
                                                 int                                     desired = (r * c +                                     1                                     ) /                                     2                                     ;                       
                                                 while                                     (min < max)                       
                                                 {                       
                                                 int                                     mid = min + (max - min) /                                     2                                     ;                       
                                                 int                                     place =                                     0                                     ;                       
                                                 int                                     get =                                     0                                     ;                       
                                   
                                                 // Find count of elements smaller than mid                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < r; ++i)                       
                                                 {                       
                                   
                                                 get = Arrays.binarySearch(m[i],mid);                       
                                   
                                                 // If element is not found in the array the                       
                                                 // binarySearch() method returns                       
                                                 // (-(insertion_point) - 1). So once we know                       
                                                 // the insertion point we can find elements                       
                                                 // Smaller than the searched element by the                       
                                                 // following calculation                       
                                                 if                                     (get <                                     0                                     )                       
                                                 get = Math.abs(get) -                                     1                                     ;                       
                                   
                                                 // If element is found in the array it returns                       
                                                 // the index(any index in case of duplicate). So we go to last                       
                                                 // index of element which will give  the number of                       
                                                 // elements smaller than the number including                       
                                                 // the searched element.                       
                                                 else                       
                                                 {                       
                                                 while                                     (get < m[i].length && m[i][get] == mid)                       
                                                 get +=                                     1                                     ;                       
                                                 }                       
                                   
                                                 place = place + get;                       
                                                 }                       
                                   
                                                 if                                     (place < desired)                       
                                                 min = mid +                                     1                                     ;                       
                                                 else                       
                                                 max = mid;                       
                                                 }                       
                                                 return                                     min;                       
                                                 }                       
                                   
                                                 // Driver Program to test above method.                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     r =                                     3                                     , c =                                     3                                     ;                       
                                                 int                                     m[][]= { {                                     1                                     ,                                     3                                     ,                                     5                                     }, {                                     2                                     ,                                     6                                     ,                                     9                                     }, {                                     3                                     ,                                     6                                     ,                                     9                                     } };                       
                                   
                                                 System.out.println(                                     "Median is "                                     + binaryMedian(m, r, c));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sumit Ghosh                       

Python3

                         # Python program to find median of matrix                       
                         # sorted row wise                       
           
                         from                                     bisect                                     import                                     bisect_right as upper_bound                       
           
                         MAX                                     =                                     100                                     ;                       
           
                         # Function to find median in the matrix                       
                         def                                     binaryMedian(m, r, d):                       
                                                 mi                                     =                                     m[                                     0                                     ][                                     0                                     ]                       
                                                 mx                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (r):                       
                                                 if                                     m[i][                                     0                                     ] < mi:                       
                                                 mi                                     =                                     m[i][                                     0                                     ]                       
                                                 if                                     m[i][d                                     -                                     1                                     ] > mx :                       
                                                 mx                                     =                                     m[i][d                                     -                                     1                                     ]                       
                                   
                                                 desired                                     =                                     (r                                     *                                     d                                     +                                     1                                     )                                     /                                     /                                     2                       
                                   
                                                 while                                     (mi < mx):                       
                                                 mid                                     =                                     mi                                     +                                     (mx                                     -                                     mi)                                     /                                     /                                     2                       
                                                 place                                     =                                     [                                     0                                     ];                       
                                   
                                                 # Find count of elements smaller than mid                       
                                                 for                                     i                                     in                                     range                                     (r):                       
                                                 j                                     =                                     upper_bound(m[i], mid)                       
                                                 place[                                     0                                     ]                                     =                                     place[                                     0                                     ]                                     +                                     j                       
                                                 if                                     place[                                     0                                     ] < desired:                       
                                                 mi                                     =                                     mid                                     +                                     1                       
                                                 else                                     :                       
                                                 mx                                     =                                     mid                       
                                                 print                                     (                                     "Median is"                                     , mi)                       
                                                 return                       
                                   
                         # Driver code                       
                         r, d                                     =                                     3                                     ,                                     3                       
           
                         m                                     =                                     [ [                                     1                                     ,                                     3                                     ,                                     5                                     ], [                                     2                                     ,                                     6                                     ,                                     9                                     ], [                                     3                                     ,                                     6                                     ,                                     9                                     ]]                       
                         binaryMedian(m, r, d)                       
           
                         # This code is contributed by Sachin BIsht                       

C#

                         // C# program to find median                       
                         // of a matrix sorted row wise                       
                         using                                     System;                       
                         class                                     MedianInRowSorted{                       
           
                         // Function to find median                       
                         // in the matrix                       
                         static                                     int                                     binaryMedian(                                     int                                     [,]m,                       
                                                 int                                     r,                                     int                                     c)                       
                         {                       
                                                 int                                     max =                                     int                                     .MinValue;                       
                                                 int                                     min =                                     int                                     .MaxValue;                       
           
                                                 for                                     (                                     int                                     i = 0; i < r; i++)                       
                                                 {                       
                                                 // Finding the minimum                       
                                                 // element                       
                                                 if                                     (m[i, 0] < min)                       
                                                 min = m[i, 0];                       
           
                                                 // Finding the maximum                       
                                                 // element                       
                                                 if                                     (m[i, c - 1] > max)                       
                                                 max = m[i, c - 1];                       
                                                 }                       
           
                                                 int                                     desired = (r * c + 1) / 2;                       
                                                 while                                     (min < max)                       
                                                 {                       
                                                 int                                     mid = min + (max - min) / 2;                       
                                                 int                                     place = 0;                       
                                                 int                                     get                                     = 0;                       
           
                                                 // Find count of elements                       
                                                 // smaller than mid                       
                                                 for                                     (                                     int                                     i = 0; i < r; ++i)                       
                                                 {                       
                                                 get                                     = Array.BinarySearch(                       
                                                 GetRow(m, i), mid);                       
           
                                                 // If element is not found                       
                                                 // in the array the binarySearch()                       
                                                 // method returns (-(insertion_                       
                                                 // point) - 1). So once we know                       
                                                 // the insertion point we can                       
                                                 // find elements Smaller than                       
                                                 // the searched element by the                       
                                                 // following calculation                       
                                                 if                                     (                                     get                                     < 0)                       
                                                 get                                     = Math.Abs(                                     get                                     ) - 1;                       
           
                                                 // If element is found in the                       
                                                 // array it returns the index(any                       
                                                 // index in case of duplicate). So                       
                                                 // we go to last index of element                       
                                                 // which will give  the number of                       
                                                 // elements smaller than the number                       
                                                 // including the searched element.                       
                                                 else                       
                                                 {                       
                                                 while                                     (                                     get                                     < GetRow(m, i).GetLength(0) &&                       
                                                 m[i,                                     get                                     ] == mid)                       
                                                 get                                     += 1;                       
                                                 }                       
           
                                                 place = place +                                     get                                     ;                       
                                                 }                       
           
                                                 if                                     (place < desired)                       
                                                 min = mid + 1;                       
                                                 else                       
                                                 max = mid;                       
                                                 }                       
                                                 return                                     min;                       
                         }                       
           
                         public                                     static                                     int                                     [] GetRow(                                     int                                     [,] matrix,                       
                                                 int                                     row)                       
                         {                       
                                                 var                                     rowLength = matrix.GetLength(1);                       
                                                 var                                     rowVector =                                     new                                     int                                     [rowLength];                       
           
                                                 for                                     (                                     var                                     i = 0; i < rowLength; i++)                       
                                                 rowVector[i] = matrix[row, i];                       
           
                                                 return                                     rowVector;                       
                         }                       
                                   
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     r = 3, c = 3;                       
                                                 int                                     [,]m = {{1,3,5},                       
                                                 {2,6,9},                       
                                                 {3,6,9} };                       
           
                                                 Console.WriteLine(                                     "Median is "                                     +                       
                                                 binaryMedian(m, r, c));                       
                         }                       
                         }                       
           
                         // This code is contributed by Princi Singh                       

Javascript

                         <script>                       
           
                         // Javascript program to find median                       
                         // of a matrix sorted row wise                       
           
           
                         // Function to find median                       
                         // in the matrix                       
                         function                                     binaryMedian(m, r, c)                       
                         {                       
                                                 var                                     max = -1000000000;                       
                                                 var                                     min = 1000000000;                       
           
                                                 for                                     (                                     var                                     i = 0; i < r; i++)                       
                                                 {                       
                                                 // Finding the minimum                       
                                                 // element                       
                                                 if                                     (m[i][0] < min)                       
                                                 min = m[i][0];                       
           
                                                 // Finding the maximum                       
                                                 // element                       
                                                 if                                     (m[i] > max)                       
                                                 max = m[i];                       
                                                 }                       
           
                                                 var                                     desired =  parseInt((r * c + 1) / 2);                       
                                                 while                                     (min < max)                       
                                                 {                       
                                                 var                                     mid = min + parseInt((max - min) / 2);                       
                                                 var                                     place = 0;                       
                                                 var                                     get = 0;                       
           
                                                 // Find count of elements                       
                                                 // smaller than mid                       
                                                 for                                     (                                     var                                     i = 0; i < r; ++i)                       
                                                 {                       
                                                 var                                     tmp = GetRow(m, i);                       
                                                 for                                     (                                     var                                     j = tmp.length; j>=0; j--)                       
                                                 {                       
                                                 if                                     (tmp[j] <= mid)                       
                                                 {                       
                                                 get = j+1;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // If element is not found                       
                                                 // in the array the binarySearch()                       
                                                 // method returns (-(insertion_                       
                                                 // point) - 1). So once we know                       
                                                 // the insertion point we can                       
                                                 // find elements Smaller than                       
                                                 // the searched element by the                       
                                                 // following calculation                       
                                                 if                                     (get < 0)                       
                                                 get = Math.abs(get) - 1;                       
           
                                                 // If element is found in the                       
                                                 // array it returns the index(any                       
                                                 // index in case of duplicate). So                       
                                                 // we go to last index of element                       
                                                 // which will give  the number of                       
                                                 // elements smaller than the number                       
                                                 // including the searched element.                       
                                                 else                       
                                                 {                       
                                                 while                                     (get < GetRow(m, i).length &&                       
                                                 m[i][get] == mid)                       
                                                 get += 1;                       
                                                 }                       
           
                                                 place = place + get;                       
                                                 }                       
           
                                                 if                                     (place < desired)                       
                                                 min = mid + 1;                       
                                                 else                       
                                                 max = mid;                       
                                                 }                       
                                                 return                                     min;                       
                         }                       
           
                         function                                     GetRow(matrix, row)                       
                         {                       
                                                 var                                     rowLength = matrix[0].length;                       
                                                 var                                     rowVector = Array(rowLength).fill(0);                       
           
                                                 for                                     (                                     var                                     i = 0; i < rowLength; i++)                       
                                                 rowVector[i] = matrix[row][i];                       
           
                                                 return                                     rowVector;                       
                         }                       
                                   
                         // Driver code                       
                         var                                     r = 3, c = 3;                       
                         var                                     m = [[1,3,5],                       
                                                 [2,6,9],                       
                                                 [3,6,9]];                       
                         document.write(                                     "Median is "                                     +                       
                                                 binaryMedian(m, r, c));                       
           
           
                         // This code is contributed by rutvik_56.                       
                         </script>                       

输出

Median is 5

时间复杂性 ：O（32*r*log（c））。上限函数将花费log（c）时间，并针对每一行执行。由于数字的最大值为32位，所以从最小值到最大值的二进制搜索将在最多32（log2（2^32）=32）个操作中执行。 辅助空间 ：O（1）

本文由 阿卡什·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章