【HackerRank】Closest Numbers
Sorting is often useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses also.
Challenge
Given a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.
Input Format
There will be two lines of input:
- n - the size of the list
- array - the n numbers of the list
Output Format
Output the pairs of numbers with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line (consecutively) with just a single space between each pair of numbers. If there's a number which lies in two pair, print it two times (see sample case #3 for explanation).
Constraints
10 <= n <= 200000
-(107) <= x <= (107), where x ∈ array
array[i] != array[j], 0 <= i, j < N, and i != j
水题:维护一个ArrayList和记录当前最小距离的变量miniDist,每当i和i+1两个数的距离和miniDist相等时,把i放到ArrayList里面;当两个数距离小于miniDist时,把ArrayList清空,i放进去,并更新miniDist;最后根据ArrayList输出答案。
代码如下:
import java.util.*; public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] ar = new int[n];
for(int i = 0;i < n;i++)
ar[i]= in.nextInt(); Arrays.sort(ar);
ArrayList<Integer> index = new ArrayList<Integer>();
int miniDis = Integer.MAX_VALUE;
for(int i = 0;i < n-1;i++){
if(ar[i+1]-ar[i] < miniDis){
index.clear();
index.add(i);
miniDis = ar[i+1]-ar[i];
}
else if(ar[i+1]-ar[i]==miniDis)
index.add(i);
}
for(int i:index){
System.out.printf("%d %d ", ar[i],ar[i+1]);
}
System.out.println(); }
}
最新文章
- iOS 后台处理
- NSArray与NSMutableArray 数组与可变数组
- C#变量类型
- 如何自定义wordpress登录界面的Logo
- mysql的存储过程
- Position a child div relative to parent container in CSS: [设置 子DIV位置 跟 父DIV相关联]
- zookeeper 配置详解
- 【转】C#程序打包安装部署之添加注册表项
- BZOJ3105: [cqoi2013]新Nim游戏
- [Ext JS 4] 实战之Grid, Tree Gird 添加按钮列
- Build Android-x86 ICS 4 Virtualbox from Google Virtualbox Target and Intel Kernel 编译体验
- MFC中实现定时执行与提醒功能(自编代码)
- Spring之AOP二
- JAVA基础-IO流(二)
- command not found
- POJ 1236 Network of Schools(tarjan)题解
- HDU 1061 Rightmost Digit (快速幂取模)
- GDB调试基础
- Alpha阶段第1周 Scrum立会报告+燃尽图 02
- python pivot() 函数