本文主要是介绍Closest Number in Sorted Array,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
准备托福的时候果然是无聊,,,,来几道题解解乏>>>>>>>>>>>>>>>>>>
Given a target number and an integer array A sorted in ascending order, find the index i
in A such that A[i] is closest to the given target.
Return -1 if there is no element in the array.
Notice
There can be duplicate elements in the array, and we can return any of the indices with same value.
Given [1, 2, 3]
and target = 2
, return 1
.
Given [1, 4, 6]
and target = 3
, return 1
.
Given [1, 4, 6]
and target = 5
, return 1
or 2
.
Given [1, 3, 3, 4]
and target = 2
, return 0
or 1
or 2
.
java solution
using binary search algorithm to solve this problem
public class Solution {/*** @param A an integer array sorted in ascending order* @param target an integer* @return an integer*/public int closestNumber(int[] A, int target) {// Write your code hereif (A == null || A.length == 0) {return -1;}int index = util(A, target);if (index == A.length) {return A.length - 1;}if (index == 0) {return 0;}if (target - A[index - 1] < A[index] - target) {return index - 1;}return index;}private int util(int[] A, int target) {int start = 0;int end = A.length - 1;while(start + 1 < end) {int mid = start + (end - start) / 2;if (target < A[mid]) {end = mid;} else if (target > A[mid]) {start = mid;} else {end = mid;}}if (target <= A[start]) {return start;}if (target <= A[end]) {return end;}return A.length;}
}
这篇关于Closest Number in Sorted Array的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!