LintCode 898. Leftmost One - Weekly9

http://www.lintcode.com/en/problem/leftmost-one/

An interesting questions, i find it sufficient applying binary search.

	public class Solution {
	/**
	* @param arr: The 2-dimension array
	* @return: Return the column the leftmost one is located
	*/
	int getColumn(int[][] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	this.m = A.length;
	this.n = A[0].length;
	int min = A.length - 1;
	for (int i = 0; i < m; i++) {
	int index = binarySearch(A[i]);
	min = Math.min(min, index);
	}
	// return the final result
	return min;
	}
	int m;
	int n;
	int binarySearch(int[] A) {
	int left = 0;
	int right = A.length - 1;
	while (left + 1 < right) {
	int mid = (right - left) / 2 + left;
	if (A[mid] == 1) {
	right = mid;
	} else {
	left = mid;
	}
	}
	if (A[left] == 1) {
	return left;
	} else {
	return right;
	}
	}
	}

view raw LintCode 898. Leftmost One - Weekly9 - LintCode.java hosted with ❤ by GitHub