Home

LinkWorld Algorithm Blog

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

scribble