06 Feb 2018
二维数组查找元素
一、题目
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
二、解题思路
Notzuonotdied的思路
假设:args为输入的数组,what为待查询的数字,lines为总行数,columns为总列数。
首先,用二维数组的每一行的最后一个元素args[i][columns - 1]与待查询的数字what进行比较,如果相等就直接输出;如果args[i][columns - 1] > what,那就对当前行进行遍历,判断是否存在该元素。
Kotlin实现
/**
* 查找二维数组中的元素
*
* @param args 待查询的数组
* @param what 查询的数字
* */
fun find(args: Array<Array<Int>>, what: Int): Boolean {
// 如果数组为空,就直接返回
if (args.isEmpty()) return false
// 遍历行
args.forEach { array ->
run {
when {
// 判断最后一个元素是否大于what
array[array.size - 1] > what -> {
// 遍历当前行元素
array.forEach { temp ->
if (temp == what) {
print("找到了,查询的值->$what\n")
return true
}
}
}
array[array.size - 1] == what -> {
print("找到了,查询的值->$what\n")
return true
}
}
}
}
return false
}
fun main(args: Array<String>) {
val lines = 10
val columns = 10
val test: Array<Array<Int>> = Array(lines, { Array(columns) { 0 } })
for (line in 1..lines) {
for (column in 1..columns) {
test[line - 1][column - 1] = (line - 1) * columns + column
}
}
// 查看初始化的内容
test.forEach { temp ->
run {
temp.forEach { result ->
print(result)
print("\t")
}
print("\n")
}
}
if (find(test, Random().nextInt(lines * columns))) print("找到了")
else print("没有找到")
}
最后结果:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
找到了,查询的值->64
找到了
Til next time,
LinkWorld
at 17:18