K Closest Numbers In Sorted Array
2024-08-25 21:23:01
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.分析
先找到最接近的数字，使用Closest Number in Sorted Array中的函数，时间复杂度 O(LogN)
然后从当前位置，使用两个指针：i 和 j。分别向头尾遍历，直到 k 个元素被 add 进结果数组list，
时间复杂度O(min(k, A.length))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
public class Solution { /** * @param A an integer array * @param target an integer * @param k a non-negative integer * @return an integer array */ public int[] kClosestNumbers(int[] A, int target, int k) { // Write your code here int len = A.length; int j = closestNumber(A, target), i = j - 1, di, dj; int[] list = new int[Math.min(k, A.length)]; int count = 0; while(len-- != 0 && k-- != 0){ di = i < 0 ? Integer.MAX_VALUE : A[i] - target; dj = j >= A.length ? Integer.MAX_VALUE : A[j] - target; if(dj == 0 || Math.abs(dj) < Math.abs(di)){ list[count++] = A[j++]; } else{ list[count++] = A[i--]; } } return list; } private int closestNumber(int[] A, int target) { // Write your code here if(A == null || A.length == 0) return -1; int left = 0, right = A.length - 1, mid; while(left < right){ mid = left + (right - left) / 2; if(A[mid] < target){ left = mid + 1; } else{ right = mid; } } // when left == right, this is the first position that target can be insert if(right > 0 && (A[right] - target) > (target - A[right - 1])) return right - 1; else return right; }} |
最新文章
- 谈谈软件项目的dependency
- 【Java】一个小程序，计算它包含的代码所需的耗时
- nodejs net模块实现socket
- I.MX6 Linux kernel LVDS backlight enable
- XMPP——Smack[6]离线消息和离线文件的实现
- 深入理解ASP.NET MVC Day1
- awk学习笔记一：基础(转)
- xmlplus 组件设计系列之三 - 文本框
- Android TextView属性大全
- java -jar和hadoop jar的区别
- java获取某一字段日期并增加7天存入另一字段
- javascript 模板
- symfony框架
- django----Form实时更新两种方式
- What is the RESTful API ?
- Java生成静态HTML文件
- 【转】ssh-copy-id帮你建立信任
- GetLastError结果列表
- Structs2笔记①--structs的背景、structs2框架的意义、第一个helloworld
- K：求取数组中最大连续子序列和的四个算法