检测矩阵中的鞍点(saddle point).

所以说你有一个像这样的矩阵:

    0  1  2
  |---------
0 | 9  8  7
1 | 5  3  2     <--- saddle point at (1,0)
2 | 6  6  7

它在(1,0)处有一个鞍点.

它被称为”鞍点”,因为它是该 行 最大数,也是该 列 的最小数。

矩阵可以具有零个或多个鞍点.

您的代码应该能够为任何给定矩阵提供所有鞍点的(可能为空)列表。

矩阵可以具有不同数量的行和列(非正方形)。

请注意,您可能会在线找到矩阵鞍点的其他定义,但本练习的测试遵循上述明确的定义.

J Dalbey 的编程实践问题http://users.csc.calpoly.edu/~jdalbey/103/Projects/ProgrammingPractice.html

pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
   unimplemented!(
       "find the saddle points of the following matrix: {:?}",
       input
   )
}

# #![allow(unused_variables)]
#fn main() {
// We don't care about order
fn find_sorted_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
   let mut result = find_saddle_points(input);
   result.sort();
   result
}

#[test]
fn identify_single_saddle_point() {
   let input = vec![vec![9, 8, 7], vec![5, 3, 2], vec![6, 6, 7]];
   assert_eq!(vec![(1, 0)], find_saddle_points(&input));
}

#[test]
//#[ignore]
fn identify_empty_matrix() {
   let input = vec![vec![], vec![], vec![]];
   let expected: Vec<(usize, usize)> = Vec::new();
   assert_eq!(expected, find_saddle_points(&input));
}

#[test]
//#[ignore]
fn identify_lack_of_saddle_point() {
   let input = vec![vec![1, 2, 3], vec![3, 1, 2], vec![2, 3, 1]];
   let expected: Vec<(usize, usize)> = Vec::new();
   assert_eq!(expected, find_saddle_points(&input));
}

#[test]
//#[ignore]
fn multiple_saddle_points_in_col() {
   let input = vec![vec![4, 5, 4], vec![3, 5, 5], vec![1, 5, 4]];
   assert_eq!(
       vec![(0, 1), (1, 1), (2, 1)],
       find_sorted_saddle_points(&input)
   );
}

#[test]
//#[ignore]
fn multiple_saddle_points_in_row() {
   let input = vec![vec![6, 7, 8], vec![5, 5, 5], vec![7, 5, 6]];
   assert_eq!(
       vec![(1, 0), (1, 1), (1, 2)],
       find_sorted_saddle_points(&input)
   );
}

#[test]
//#[ignore]
fn identify_bottom_right_saddle_point() {
   let input = vec![vec![8, 7, 9], vec![6, 7, 6], vec![3, 2, 5]];
   assert_eq!(vec![(2, 2)], find_saddle_points(&input));
}

// track specific as of v1.3
#[test]
//#[ignore]
fn non_square_matrix_high() {
   let input = vec![vec![1, 5], vec![3, 6], vec![2, 7], vec![3, 8]];
   assert_eq!(vec![(0, 1)], find_saddle_points(&input));
}

#[test]
//#[ignore]
fn non_square_matrix_wide() {
   let input = vec![vec![3, 1, 3], vec![3, 2, 4]];
   assert_eq!(vec![(0, 0), (0, 2)], find_sorted_saddle_points(&input));
}

#[test]
//#[ignore]
fn single_column_matrix() {
   let input = vec![vec![2], vec![1], vec![4], vec![1]];
   assert_eq!(vec![(1, 0), (3, 0)], find_saddle_points(&input));
}

#[test]
//#[ignore]
fn single_row_matrix() {
   let input = vec![vec![2, 5, 3, 5]];
   assert_eq!(vec![(0, 1), (0, 3)], find_saddle_points(&input));
}

#}

# #![allow(unused_variables)]
#fn main() {
pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
   let mut saddle_points = Vec::new();

   let width = input.len();
   let height = input[0].len();

   for i in 0..width {
       for j in 0..height {
           let column = input.iter().map(|x| x[j]).collect::<Vec<u64>>();
           let row = &input[i];

           let max = row.iter().max().unwrap();
           let min = column.iter().min().unwrap();

           let value = input[i][j];

           if value >= *max && value <= *min {
               saddle_points.push((i, j));
           }
       }
   }
   saddle_points
}

#}