面接に必要な基礎知識-2 D配列での検索

タイトル

        ，                 ，                 。       ，                ，            。

問題解決の考え方:

             。             ，      ；             ，          ；             ，          。

コード#コード#

/**
 * 
 */
package com.jason.interviewQuestions.basicKnowledge;

/**
 *         ，                 ，                 。       ，                ，            。
 * @author jason zhang
 *
 */
public class FindInPartiallySortedMatirx {

	/**
	 *         
	 * @param matirx       
	 * @param rows      
	 * @param columns      
	 * @param number      
	 * @return
	 */
	boolean findFromUpperRight(int[][] matrix, int rows, int columns, int number) {
		boolean found = false;
		if (matrix != null && rows > 0 && columns > 0) {
			int row = 0;
			int column = columns - 1;
			while (row < rows && column >= 0) {
				if (matrix[row][column] == number) {
					found = true;
					System.out.println("find the number at " + (row+1) + " row and " + (column+1) + " column");
					break;
				} else if (matrix[row][column] > number) {
					//              ，          
					column--;
				} else {
					//              ，          
					row++;
				}
			}
		}
		return found;
	}
	
	/**
	 *         
	 * @param matirx       
	 * @param rows      
	 * @param columns      
	 * @param number      
	 * @return
	 */
	boolean findFromLeftLower(int[][] matrix, int rows, int columns, int number) {
		boolean found = false;
		if (matrix != null && rows > 0 && columns > 0) {
			int row = rows - 1;
			int column = 0;
			while (row >= 0 && column < columns) {
				if (matrix[row][column] == number) {
					found = true;
					System.out.println("find the number at " + (row+1) + " row and " + (column+1) + " column");
					break;
				} else if (matrix[row][column] > number) {
					//              ，          
					row--;
				} else {
					//              ，          
					column++;
					
				}
			}
		}
		return found;
	}
}

テストコード

package com.jason.interviewQuestions.basicKnowledge;

import junit.framework.TestCase;

public class FindInPartiallySortedMatirxTest extends TestCase {

	private FindInPartiallySortedMatirx fipsm;
	private int[][] matrix = {
			{1,2,8,9},
			{2,4,9,12},
			{4,7,10,13},
			{6,8,11,15}
	};;
	protected void setUp() throws Exception {
		super.setUp();
		this.fipsm = new FindInPartiallySortedMatirx();
	}

	public void testFindFromUpperRight() {
		int number = 15;
		boolean find = this.fipsm.findFromUpperRight(matrix, 4, 4, number);
		super.assertTrue(find);
		
	}
	
	public void testFindFromUpperRightNF() {
		int number = 3;
		boolean find = this.fipsm.findFromUpperRight(matrix, 4, 4, number);
		super.assertFalse(find);
		
	}
	
	public void testfindFromLeftLower() {
		int number = 7;
		boolean find = this.fipsm.findFromUpperRight(matrix, 4, 4, number);
		super.assertTrue(find);
		
	}
	
	public void testfindFromLeftLowerNF() {
		int number = 3;
		boolean find = this.fipsm.findFromUpperRight(matrix, 4, 4, number);
		super.assertFalse(find);
		
	}

}

コメント:
テーマは何海濤著の「剣指offer」から来て、本の中でcを使って実現して、本文はjavaを使って実現します.