查找按列/按行排序的矩阵M[]中的负数。假设M有n行和M列。 例子：
null
Input: M = [-3, -2, -1, 1] [-2, 2, 3, 4] [4, 5, 7, 8]Output : 4We have 4 negative numbers in this matrix
我们强烈建议您尽量减少浏览器，并先自己尝试。 天真的解决方案 这是一个幼稚的、非最优的解决方案。 我们从左上角开始，从左到右，从上到下，一个接一个地计算负数。 举一个例子：
[-3, -2, -1, 1][-2, 2, 3, 4][4, 5, 7, 8]Evaluation process[?, ?, ?, 1][?, 2, 3, 4][4, 5, 7, 8]
以下是上述理念的实施：
C++
// CPP implementation of Naive method // to count of negative numbers in // M[n][m] #include <bits/stdc++.h> using namespace std; int countNegative( int M[][4], int n, int m) { int count = 0; // Follow the path shown using // arrows above for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (M[i][j] < 0) count += 1; // no more negative numbers // in this row else break ; } } return count; } // Driver program to test above functions int main() { int M[3][4] = { { -3, -2, -1, 1 }, { -2, 2, 3, 4 }, { 4, 5, 7, 8 } }; cout << countNegative(M, 3, 4); return 0; } // This code is contributed by Niteesh Kumar |
JAVA
// Java implementation of Naive method // to count of negative numbers in // M[n][m] import java.util.*; import java.lang.*; import java.io.*; class GFG { static int countNegative( int M[][], int n, int m) { int count = 0 ; // Follow the path shown using // arrows above for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { if (M[i][j] < 0 ) count += 1 ; // no more negative numbers // in this row else break ; } } return count; } // Driver program to test above functions public static void main(String[] args) { int M[][] = { { - 3 , - 2 , - 1 , 1 }, { - 2 , 2 , 3 , 4 }, { 4 , 5 , 7 , 8 } }; System.out.println(countNegative(M, 3 , 4 )); } } // This code is contributed by Chhavi |
Python3
# Python implementation of Naive method to count of # negative numbers in M[n][m] def countNegative(M, n, m): count = 0 # Follow the path shown using arrows above for i in range (n): for j in range (m): if M[i][j] < 0 : count + = 1 else : # no more negative numbers in this row break return count # Driver code M = [ [ - 3 , - 2 , - 1 , 1 ], [ - 2 , 2 , 3 , 4 ], [ 4 , 5 , 7 , 8 ] ] print (countNegative(M, 3 , 4 )) |
C#
// C# implementation of Naive method // to count of negative numbers in // M[n][m] using System; class GFG { // Function to count // negative number static int countNegative( int [, ] M, int n, int m) { int count = 0; // Follow the path shown // using arrows above for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (M[i, j] < 0) count += 1; // no more negative numbers // in this row else break ; } } return count; } // Driver Code public static void Main() { int [, ] M = { { -3, -2, -1, 1 }, { -2, 2, 3, 4 }, { 4, 5, 7, 8 } }; Console.WriteLine(countNegative(M, 3, 4)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation of Naive method // to count of negative numbers in // M[n][m] function countNegative( $M , $n , $m ) { $count = 0; // Follow the path shown using // arrows above for ( $i = 0; $i < $n ; $i ++) { for ( $j = 0; $j < $m ; $j ++) { if ( $M [ $i ][ $j ] < 0 ) $count += 1; // no more negative numbers // in this row else break ; } } return $count ; } // Driver Code $M = array ( array (-3, -2, -1, 1), array (-2, 2, 3, 4), array (4, 5, 7, 8)); echo countNegative( $M , 3, 4); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript implementation of Naive method // to count of negative numbers in // M[n][m] function countNegative(M,n,m) { let count = 0; // Follow the path shown using // arrows above for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (M[i][j] < 0) count += 1; // no more negative numbers // in this row else break ; } } return count; } // Driver program to test above functions let M = [[ -3, -2, -1, 1 ], [ -2, 2, 3, 4 ], [ 4, 5, 7, 8 ]]; document.write(countNegative(M, 3, 4)); // This code is contributed by sravan kumar </script> |
输出：
4
在这种方法中，我们遍历所有元素，因此，在最坏的情况下（当矩阵中的所有数字都为负数时），这需要O（n*m）时间。 最优解 这里有一个更有效的解决方案：
- 我们从右上角开始，找到第一行最后一个负数的位置。
- 利用这些信息，我们可以找到第二行最后一个负数的位置。
- 我们不断重复这个过程，直到负数用完或到达最后一行。
With the given example:[-3, -2, -1, 1][-2, 2, 3, 4][4, 5, 7, 8]Here's the idea:[-3, -2, ?, ?] -> Found 3 negative numbers in this row[ ?, ?, ?, 4] -> Found 1 negative number in this row[ ?, 5, 7, 8] -> No negative numbers in this row
C++
// CPP implementation of Efficient // method to count of negative numbers // in M[n][m] #include <bits/stdc++.h> using namespace std; int countNegative( int M[][4], int n, int m) { // initialize result int count = 0; // Start with top right corner int i = 0; int j = m - 1; // Follow the path shown using // arrows above while (j >= 0 && i < n) { if (M[i][j] < 0) { // j is the index of the // last negative number // in this row. So there // must be ( j+1 ) count += j + 1; // negative numbers in // this row. i += 1; } // move to the left and see // if we can find a negative // number there else j -= 1; } return count; } // Driver program to test above functions int main() { int M[3][4] = { { -3, -2, -1, 1 }, { -2, 2, 3, 4 }, { 4, 5, 7, 8 } }; cout << countNegative(M, 3, 4); return 0; } // This code is contributed by Niteesh Kumar |
JAVA
// Java implementation of Efficient // method to count of negative numbers // in M[n][m] import java.util.*; import java.lang.*; import java.io.*; class GFG { static int countNegative( int M[][], int n, int m) { // initialize result int count = 0 ; // Start with top right corner int i = 0 ; int j = m - 1 ; // Follow the path shown using // arrows above while (j >= 0 && i < n) { if (M[i][j] < 0 ) { // j is the index of the // last negative number // in this row. So there // must be ( j+1 ) count += j + 1 ; // negative numbers in // this row. i += 1 ; } // move to the left and see // if we can find a negative // number there else j -= 1 ; } return count; } // Driver program to test above functions public static void main(String[] args) { int M[][] = { { - 3 , - 2 , - 1 , 1 }, { - 2 , 2 , 3 , 4 }, { 4 , 5 , 7 , 8 } }; System.out.println(countNegative(M, 3 , 4 )); } } // This code is contributed by Chhavi |
Python3
# Python implementation of Efficient method to count of # negative numbers in M[n][m] def countNegative(M, n, m): count = 0 # initialize result # Start with top right corner i = 0 j = m - 1 # Follow the path shown using arrows above while j > = 0 and i < n: if M[i][j] < 0 : # j is the index of the last negative number # in this row. So there must be ( j + 1 ) count + = (j + 1 ) # negative numbers in this row. i + = 1 else : # move to the left and see if we can # find a negative number there j - = 1 return count # Driver code M = [ [ - 3 , - 2 , - 1 , 1 ], [ - 2 , 2 , 3 , 4 ], [ 4 , 5 , 7 , 8 ] ] print (countNegative(M, 3 , 4 )) |
C#
// C# implementation of Efficient // method to count of negative // numbers in M[n][m] using System; class GFG { // Function to count // negative number static int countNegative( int [, ] M, int n, int m) { // initialize result int count = 0; // Start with top right corner int i = 0; int j = m - 1; // Follow the path shown // using arrows above while (j >= 0 && i < n) { if (M[i, j] < 0) { // j is the index of the // last negative number // in this row. So there // must be ( j + 1 ) count += j + 1; // negative numbers in // this row. i += 1; } // move to the left and see // if we can find a negative // number there else j -= 1; } return count; } // Driver Code public static void Main() { int [, ] M = { { -3, -2, -1, 1 }, { -2, 2, 3, 4 }, { 4, 5, 7, 8 } }; Console.WriteLine(countNegative(M, 3, 4)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation of Efficient // method to count of negative numbers // in M[n][m] function countNegative( $M , $n , $m ) { // initialize result $count = 0; // Start with top right corner $i = 0; $j = $m - 1; // Follow the path shown using // arrows above while ( $j >= 0 and $i < $n ) { if ( $M [ $i ][ $j ] < 0 ) { // j is the index of the // last negative number // in this row. So there // must be ( j+1 ) $count += $j + 1; // negative numbers in // this row. $i += 1; } // move to the left and see // if we can find a negative // number there else $j -= 1; } return $count ; } // Driver Code $M = array ( array (-3, -2, -1, 1), array (-2, 2, 3, 4), array (4, 5, 7, 8)); echo countNegative( $M , 3, 4); return 0; // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript implementation of Efficient // method to count of negative numbers // in M[n][m]q function countNegative(M, n, m) { // initialize result let count = 0; // Start with top right corner let i = 0; let j = m - 1; // Follow the path shown using // arrows above while (j >= 0 && i < n) { if (M[i][j] < 0) { // j is the index of the // last negative number // in this row. So there // must be ( j+1 ) count += j + 1; // negative numbers in // this row. i += 1; } // move to the left and see // if we can find a negative // number there else j -= 1; } return count; } let M = [ [ -3, -2, -1, 1 ], [ -2, 2, 3, 4 ], [ 4, 5, 7, 8 ] ]; document.write(countNegative(M, 3, 4)); ` // This code is contributed by decode2207. </script> |
输出：
4
有了这个解决方案，我们现在可以在O（n+m）时间内解决这个问题。 更优的解决方案 下面是一个使用二进制搜索而不是线性搜索的更有效的解决方案：
- 我们从第一行开始，使用二进制搜索找到第一行中最后一个负数的位置。
- 利用这些信息，我们只需运行二进制搜索，直到找到上一行中最后一个负数的位置，就可以找到第二行中最后一个负数的位置。
- 我们不断重复这个过程，直到负数用完或到达最后一行。
With the given example:[-3, -2, -1, 1][-2, 2, 3, 4][4, 5, 7, 8]Here's the idea:1. Count is initialized to 02. Binary search on full 1st row returns 2 as the index of last negative integer, and we increase count to 0+(2+1) = 3.3. For 2nd row, we run binary search from index 0 to index 2 and it returns 0 as the index of last negative integer. We increase the count to 3+(0+1) = 4;4. For 3rd row, first element is > 0, so we end the loop here.
C++
// C++ implementation of More efficient // method to count number of negative numbers // in row-column sorted matrix M[n][m] #include<bits/stdc++.h> using namespace std; // Recursive binary search to get last negative // value in a row between a start and an end int getLastNegativeIndex( int array[], int start, int end, int n) { // Base case if (start == end) { return start; } // Get the mid for binary search int mid = start + (end - start) / 2; // If current element is negative if (array[mid] < 0) { // If it is the rightmost negative // element in the current row if (mid + 1 < n && array[mid + 1] >= 0) { return mid; } // Check in the right half of the array return getLastNegativeIndex(array, mid + 1, end, n); } else { // Check in the left half of the array return getLastNegativeIndex(array, start, mid - 1, n); } } // Function to return the count of // negative numbers in the given matrix int countNegative( int M[][4], int n, int m) { // Initialize result int count = 0; // To store the index of the rightmost negative // element in the row under consideration int nextEnd = m - 1; // Iterate over all rows of the matrix for ( int i = 0; i < n; i++) { // If the first element of the current row // is positive then there will be no negatives // in the matrix below or after it if (M[i][0] >= 0) { break ; } // Run binary search only until the index of last // negative Integer in the above row nextEnd = getLastNegativeIndex(M[i], 0, nextEnd, 4); count += nextEnd + 1; } return count; } // Driver code int main() { int M[][4] = { { -3, -2, -1, 1 }, { -2, 2, 3, 4 }, { 4, 5, 7, 8 } }; int r = 3; int c = 4; cout << (countNegative(M, r, c)); return 0; } // This code is contributed by Arnab Kundu |
JAVA
// Java implementation of More efficient // method to count number of negative numbers // in row-column sorted matrix M[n][m] import java.util.*; import java.lang.*; import java.io.*; class GFG { // Recursive binary search to get last negative // value in a row between a start and an end static int getLastNegativeIndex( int array[], int start, int end) { // Base case if (start == end) { return start; } // Get the mid for binary search int mid = start + (end - start) / 2 ; // If current element is negative if (array[mid] < 0 ) { // If it is the rightmost negative // element in the current row if (mid + 1 < array.length && array[mid + 1 ] >= 0 ) { return mid; } // Check in the right half of the array return getLastNegativeIndex(array, mid + 1 , end); } else { // Check in the left half of the array return getLastNegativeIndex(array, start, mid - 1 ); } } // Function to return the count of // negative numbers in the given matrix static int countNegative( int M[][], int n, int m) { // Initialize result int count = 0 ; // To store the index of the rightmost negative // element in the row under consideration int nextEnd = m - 1 ; // Iterate over all rows of the matrix for ( int i = 0 ; i < n; i++) { // If the first element of the current row // is positive then there will be no negatives // in the matrix below or after it if (M[i][ 0 ] >= 0 ) { break ; } // Run binary search only until the index of last // negative Integer in the above row nextEnd = getLastNegativeIndex(M[i], 0 , nextEnd); count += nextEnd + 1 ; } return count; } // Driver code public static void main(String[] args) { int M[][] = { { - 3 , - 2 , - 1 , 1 }, { - 2 , 2 , 3 , 4 }, { 4 , 5 , 7 , 8 } }; int r = M.length; int c = M[ 0 ].length; System.out.println(countNegative(M, r, c)); } } // This code is contributed by Rahul Jain |
Python3
# Python3 implementation of More efficient # method to count number of negative numbers # in row-column sorted matrix M[n][m] # Recursive binary search to get last negative # value in a row between a start and an end def getLastNegativeIndex(array, start, end, n): # Base case if (start = = end): return start # Get the mid for binary search mid = start + (end - start) / / 2 # If current element is negative if (array[mid] < 0 ): # If it is the rightmost negative # element in the current row if (mid + 1 < n and array[mid + 1 ] > = 0 ): return mid # Check in the right half of the array return getLastNegativeIndex(array, mid + 1 , end, n) else : # Check in the left half of the array return getLastNegativeIndex(array, start, mid - 1 , n) # Function to return the count of # negative numbers in the given matrix def countNegative(M, n, m): # Initialize result count = 0 # To store the index of the rightmost negative # element in the row under consideration nextEnd = m - 1 # Iterate over all rows of the matrix for i in range (n): # If the first element of the current row # is positive then there will be no negatives # in the matrix below or after it if (M[i][ 0 ] > = 0 ): break # Run binary search only until the index of last # negative Integer in the above row nextEnd = getLastNegativeIndex(M[i], 0 , nextEnd, 4 ) count + = nextEnd + 1 return count # Driver code M = [[ - 3 , - 2 , - 1 , 1 ],[ - 2 , 2 , 3 , 4 ],[ 4 , 5 , 7 , 8 ]] r = 3 c = 4 print (countNegative(M, r, c)) # This code is contributed by shubhamsingh10 |
C#
// C# implementation of More efficient // method to count number of negative numbers // in row-column sorted matrix M[n,m] using System; using System.Collections.Generic; class GFG { // Recursive binary search to get last negative // value in a row between a start and an end static int getLastNegativeIndex( int []array, int start, int end) { // Base case if (start == end) { return start; } // Get the mid for binary search int mid = start + (end - start) / 2; // If current element is negative if (array[mid] < 0) { // If it is the rightmost negative // element in the current row if (mid + 1 < array.GetLength(0) && array[mid + 1] >= 0) { return mid; } // Check in the right half of the array return getLastNegativeIndex(array, mid + 1, end); } else { // Check in the left half of the array return getLastNegativeIndex(array, start, mid - 1); } } // Function to return the count of // negative numbers in the given matrix static int countNegative( int [,]M, int n, int m) { // Initialize result int count = 0; // To store the index of the rightmost negative // element in the row under consideration int nextEnd = m - 1; // Iterate over all rows of the matrix for ( int i = 0; i < n; i++) { // If the first element of the current row // is positive then there will be no negatives // in the matrix below or after it if (M[i, 0] >= 0) { break ; } // Run binary search only until the index of last // negative int in the above row nextEnd = getLastNegativeIndex(GetRow(M, i), 0, nextEnd); count += nextEnd + 1; } return count; } 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 [,]M = { { -3, -2, -1, 1 }, { -2, 2, 3, 4 }, { 4, 5, 7, 8 } }; int r = M.GetLength(0); int c = M.GetLength(1); Console.WriteLine(countNegative(M, r, c)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of More efficient // method to count number of negative numbers // in row-column sorted matrix M[n,m] // Recursive binary search to get last negative // value in a row between a start and an end function getLastNegativeIndex(array, start, end) { // Base case if (start == end) { return start; } // Get the mid for binary search var mid = start + parseInt((end - start) / 2); // If current element is negative if (array[mid] < 0) { // If it is the rightmost negative // element in the current row if (mid + 1 < array.length && array[mid + 1] >= 0) { return mid; } // Check in the right half of the array return getLastNegativeIndex(array, mid + 1, end); } else { // Check in the left half of the array return getLastNegativeIndex(array, start, mid - 1); } } // Function to return the count of // negative numbers in the given matrix function countNegative(M, n, m) { // Initialize result var count = 0; // To store the index of the rightmost negative // element in the row under consideration var nextEnd = m - 1; // Iterate over all rows of the matrix for ( var i = 0; i < n; i++) { // If the first element of the current row // is positive then there will be no negatives // in the matrix below or after it if (M[i][0] >= 0) { break ; } // Run binary search only until the index of last // negative int in the above row nextEnd = getLastNegativeIndex(GetRow(M, i), 0, nextEnd); count += nextEnd + 1; } return count; } 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 M = [ [ -3, -2, -1, 1 ], [ -2, 2, 3, 4 ], [ 4, 5, 7, 8 ] ]; var r = M.length; var c = M[0].length; document.write(countNegative(M, r, c)); </script> |
输出：
4
在这里，我们用二进制搜索代替了最后一个负数的线性搜索。这将改善最坏情况，使最坏情况保持在O（nlog（m））。 本文由 杉下YK 和 分析师拉胡尔贾殷 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
