剣指offerアルゴリズムjavaは2次元配列の中の検索を実現します
剣指offerアルゴリズムjava実装
タイトル:
2 D配列では、各行が左から右に増加し、各列が上から増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列に関数が含まれているかどうかを判断してください.
たとえば、次の2 D配列は、行ごと、列ごとにインクリメンタルソートです.この配列で数字7を検索するとtrueが返され、配列5を検索すると、配列に数字が含まれていないためfalseが返されます.
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
私たちが1つの問題を解決する時、1つのとても有効な方法は1つの具体的な問題から着手して、簡単な具体的な例を分析することを通じて、普遍的な法則を探そうとします.
解析によれば,配列検索範囲の右上隅の数字を毎回選択し,同様に左下隅の数字を選択することができるが,検索範囲を縮小できないため,左上隅または右下隅を選択することはできない.
タイトル:
2 D配列では、各行が左から右に増加し、各列が上から増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列に関数が含まれているかどうかを判断してください.
たとえば、次の2 D配列は、行ごと、列ごとにインクリメンタルソートです.この配列で数字7を検索するとtrueが返され、配列5を検索すると、配列に数字が含まれていないためfalseが返されます.
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
私たちが1つの問題を解決する時、1つのとても有効な方法は1つの具体的な問題から着手して、簡単な具体的な例を分析することを通じて、普遍的な法則を探そうとします.
package com.ynu.www.offer;
public class FindFromMatrix {
private static int[][] sample = new int[][] { { 1, 2, 8, 9 },
{ 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
public static void printSample() {
for (int i = 0; i < sample.length; i++) {
for (int j = 0; j < sample[i].length; j++) {
System.out.print(sample[i][j] + " ");
}
System.out.println();
}
}
public static boolean getValuefromMatrix(int[][] sample, int rows,
int columns, int num) {
boolean found = false;
if (sample != null && rows > 0 && columns > 0) {
int row = 0;
int column = columns - 1;
while (row < rows && column >= 0) {
int tempValue = sample[row][column];
if (num > tempValue) {
++row;
} else if (num < tempValue) {
--column;
} else {
found = true;
break;
}
}
}
return found;
}
public static void main(String[] args) {
printSample();
System.out.println(getValuefromMatrix(sample, 4, 4, 7));
}
}
解析によれば,配列検索範囲の右上隅の数字を毎回選択し,同様に左下隅の数字を選択することができるが,検索範囲を縮小できないため,左上隅または右下隅を選択することはできない.