矩阵

矩阵问题

矩阵按层打印

• 问题描述:
  • 给定矩阵:
    1 2 3 4
    5 6 7 8
    9 10 11 12
  • 打印结果 1 2 3 4 8 12 11 10 9 5 6 7
• 思路:
  • 每次只打印一框, 直到打印结束
• 代码:

  func spiralOrderPrint(arr [][]int)  {
  	if arr == nil || len(arr) < 1 || len(arr[0]) < 1 {
  		return
  	}
  	LT, RT, LB, RB := 0, 0, len(arr) - 1,  len(arr[0]) - 1
  	for LT <= LB && RT <= RB {
  		printEdge(arr, LT, RT, LB, RB)
  		LT++
  		RT++
  		LB--
  		RB--
  	}
  }
  
  func printEdge(arr [][]int, LT, RT, LB, RB int)  {
  	if LT == LB {
  		for ; RT <= RB; RT++ {
  			fmt.Println(arr[LT][RT])
  		}
  		return
  	}
  	if RT == RB {
  		for ; LT <= LB; LT++ {
  			fmt.Println(arr[LT][RT])
  		}
  		return
  	}
  	for i := RT; i < RB; i++ {
  		fmt.Println(arr[LT][i])
  	}
  	for i := LT; i < LB; i++ {
  		fmt.Println(arr[i][RB])
  	}
  	for i := RB; i > RT; i-- {
  		fmt.Println(arr[LB][i])
  	}
  	for i := LB; i > LT; i-- {
  		fmt.Println(arr[i][RT])
  	}
  }

正方形矩阵顺时针旋转90度

• 问题描述
  • 给定矩阵:
    1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16
  • 处理后的矩阵
    13 9 5 1
    14 10 6 2
    15 11 7 3
    16 12 8 4
• 思路:
  • 每次只旋转一框, 直到旋转完成
• 代码:

  func rotateMatrix(arr [][]int) {
  	if arr == nil || len(arr) == 0  || len(arr[0]) == 0 || len(arr) != len(arr[0]) {
  		return
  	}
  	LT, RT, LB, RB := 0, 0, len(arr) - 1, len(arr[0]) - 1
  	for LT < LB && RT < RB {
  		rotateEdge(arr, LT, RT, LB, RB)
  		LT++
  		RT++
  		LB--
  		RB--
  	}
  }
  
  func rotateEdge(arr [][]int, LT, RT, LB, RB int)  {
  	if LT == LB || RT == RB {
  		return
  	}
  	for i := 0; i < RB - RT; i++] {
  		arr[LT + i][RB], arr[LB][RB - i], arr[LB - i][RT], arr[LT][RT + i] = arr[LT][RT + i], arr[LT + i][RB], arr[LB][RB - i], arr[LB - i][RT]
  	}
  }

之字型打印矩阵

• 问题描述
  • 给定矩阵:
    1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16
  • 打印结果:
    1
    2 5
    9 6 3
    4 7 10 13
    14 11 8
    12 15
    16
• 思路:
  • 每次只打印一条线, 直到打印完成
• 代码

  func MatrixZigZag(arr [][]int)  {
  	if arr == nil || len(arr) == 0 || len(arr[0]) == 0 {
  		return
  	}
  	P1L, P1R, P2L, P2R := 0, 0, 0, 0
  	flag := false
  	for P1L < len(arr) && P2L < len(arr) && P1R < len(arr[0]) && P2R < len(arr[0]) {
  		printOneLine(arr, P1L, P1R, P2L, P2R, flag)
  		flag = !flag
  		if P1R != len(arr[0]) - 1 {
  			P1R++
  		} else {
  			P1L++
  		}
  		if P2L != len(arr) - 1 {
  			P2L++
  		} else {
  			P2R++
  		}
  	}
  }
  
  func printOneLine(arr [][]int, P1L, P1R, P2L, P2R int, P1ToP2 bool) {
  	for P1L != P2L && P1R != P2R {
  		if P1ToP2 {
  			fmt.Print(arr[P1L][P1R], "  ")
  			P1L++
  			P1R--
  		} else {
  			fmt.Print(arr[P2L][P2R], "  ")
  			P2L--
  			P2R++
  		}
  	}
  	fmt.Println(arr[P1L][P1R])
  }

从一个行和列都已经排好序的二维数组中寻找指定元素是否存在

• 给定一个行和列都已经排好续的矩阵和一个数, 判断矩阵中是否有这个数
  • 矩阵例:
    1 3 5 7
    2 6 8 10
    4 9 10 12
    • 数: 6
• 思路:
  1. 从右上往左下寻找
     • 从矩阵右上角开始寻找
     • 如果数小于指定的数, 向下移动
     • 如果数大于指定的数, 向左移
  2. 从左下往右上寻找
     • 从矩阵左下角开始寻找
     • 如果数小于指定数, 向右移动
     • 如果数大于指定数, 向上移动
• 代码:

  func findNumInSortMatrix(arr [][]int, num int) (int, int) {
  	if arr == nil || len(arr) == 0 || len(arr[0]) == 0 {
  		return -1, -1
  	}
  	x, y := len(arr) - 1, 0
  	for x >= 0 && y < len(arr[0]) {
  		if arr[x][y] == num {
  			return x, y
  		}
  		if arr[x][y] > num {
  			x--
  		}
  		if arr[x][y] < num {
  			y++
  		}
  	}
  	return -1, -1
  }