K Closest Numbers In Sorted Array

Leave a comment

October 3, 2016 by oneOokay

binary search 第二遍刷完了。唉。

Given a target number, a non-negative integer k and an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.

Example

Given A = [1, 2, 3], target = 2 and k = 3, return [2, 1, 3].

Given A = [1, 4, 6, 8], target = 3 and k = 3, return [4, 1, 6].

我写的略微有点复杂:

  • findIndex:若找到target,return target index,若没找到target,return离它最近的一个值的index
  • 主函数:先把result[0] = index, 然后left = index – 1; right = index + 1; for-loop把result[i]补满。

另一个改善一点的:

  • findIndex:当target<= start的时候,return start;若start < target <= end时,return end;若target > end时,return end. (此时target不存在于A中,且大于A的最大值)
  • 主函数:left = index – 1; right = index.  for-loop把result[i]补满。

BETTER ONE:

public int[] kClosestNumbers(int[] A, int target, int k) {
int[] result = new int[k];
if (A == null || A.length == 0 || k == 0) {
return result;
}

int index = findIndex(A, target);
int start = index – 1;
int end = index;
for (int i = 0; i < k; i ++) {
if (start < 0) {
result[i] = A[end ++];
}else if (end >= A.length) {
result[i] = A[start –];
}else {
if (target – A[start] > A[end] – target) {
result[i] = A[end ++];
}else {
result[i] = A[start –];
}}}
return result;
}

private int findIndex(int[] A, int target) {
int start = 0;
int end = A.length – 1;
while (start + 1 < end) {
int mid = start + (end – start) / 2;
if (A[mid] == target) {
return mid;
}
if (A[mid] > target) {
end = mid;
}else {
start = mid;
}}
if (A[start] >= target) {
return start;
}
if (target <= A[end]) {
if (Math.abs(A[start] – target) == Math.abs(A[end] – target)) {
return start;
} else if (Math.abs(A[start] – target) < Math.abs(A[end] – target)) {
return start;
}else {
return end;
}}
return end; //target >= A[end]
}

我的:

public int[] kClosestNumbers(int[] A, int target, int k) {
int[] result = new int[k];
if (A == null || A.length == 0 || k == 0) {
return result;
}

int index = findIndex(A, target);
int start = index – 1;
int end = index + 1;
result[0] = A[index];
for (int i = 1; i < k; i ++) {
if (start < 0) {
result[i] = A[end ++];
}else if (end >= A.length) {
result[i] = A[start –];
}else {
if (target – A[start] > A[end] – target) {
result[i] = A[end ++];
}else {
result[i] = A[start –];
}}}
return result;
}

private int findIndex(int[] A, int target) {
int start = 0;
int end = A.length – 1;
while (start + 1 < end) {
int mid = start + (end – start) / 2;
if (A[mid] == target) {
return mid;
}

if (A[mid] > target) {
end = mid;
}else {
start = mid;
}}
if (A[start] >= target) {
return start;
}
if (A[start] < target && target < A[end]) {
if (Math.abs(A[start] – target) == Math.abs(A[end] – target)) {
return start;
} else if (Math.abs(A[start] – target) < Math.abs(A[end] – target)) {
return start;
}else {
return end;
}}
return end;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: