首页 > 代码库 > 绝对值最小--Java实现
绝对值最小--Java实现
题目详情
给你一个数组A[n],请你计算出ans=min(|A[i]+A[j]|)(0<=i,j<n).
例如:A={1, 4, -3},
则:
|A[0] + A[0]| = |1 + 1| = 2.
|A[0] + A[1]| = |1 + 4| = 5.
|A[0] + A[2]| = |1 + (-3)| = 2.
|A[1] + A[1]| = |4 + 4| = 8.
|A[1] + A[2]| = |4 + (-3)| = 1.
|A[2] + A[2]| = |(-3) + (-3)| = 6.
所以ans=1.
输入描述:
有多组测数数据,每组数据有两行,第一行包含一个正整数n(0<n<=100000),第二行包含n个整数,分别表示A[0],A[1],A[2],....,A[n-1],(|A[i]|<2^30)。
输入以文件结束。
输出描述:
对于每组数据,输出相应的答案。
答题说明
输入样例:
3
1 4 -3
1
2
3
-1 -2 -5
3
1 2 3
2
0 5
输出样例:
1
4
2
2
0
实现思路:
1.穷举思路:
对数组中每对数值的和的绝对值进行比较,选出最小的。本来以为这样为超时,但没想到通过了。。。
Java代码:
代码获取地址:https://github.com/liuhao123/ACM
package com.liuhao.acm.csdn; import java.io.BufferedInputStream; import java.util.Scanner; /** * @author liuhao * 绝对值最小 * 给你一个数组A[n],请你计算出ans=min(|A[i]+A[j]|)(0<=i,j<n). */ public class MinAbsoluteValue2 { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in)); while(sc.hasNext()){ int n = sc.nextInt(); int[] inputArr = new int[n]; for(int i=0; i<n;i++){ inputArr[i] = sc.nextInt(); } System.out.println(minAbsoluteValue(inputArr)); } sc.close(); // //测试数据 // int[] testArr1 = {1,2,3,4,23,45,67,4}; // int[] testArr2 = {-32,-34,-53,-354,-67}; // int[] testArr3 = {1,2,3,4,23,45,67,0,-32,-34,6,-53,-354,-67}; // int[] testArr4 = {1,2,3,4,23,45,67,-32,-34,6,-53,-354,-67}; // int[] testArr5 = {1,2,3,4,23,45,67,-32,-34,6,-53,-354,-68}; // // System.out.println(minAbsoluteValue(testArr1)); // System.out.println(minAbsoluteValue(testArr2)); // System.out.println(minAbsoluteValue(testArr3)); // System.out.println(minAbsoluteValue(testArr4)); // System.out.println(minAbsoluteValue(testArr5)); } private static int minAbsoluteValue(int[] inputArr){ int ans = Math.abs(2 * inputArr[0]); for(int i=0;i<inputArr.length;i++){ for(int j=i; j<inputArr.length;j++){ if(ans > Math.abs(inputArr[i] + inputArr[j])){ ans = Math.abs(inputArr[i] + inputArr[j]); } } } return ans; } }
2.对数组中的数据进行分析
若数组中有0,则结果肯定为0;
否则,若全是正数或全是负数,则结果是其中的绝对值最小的;
若既有正数又有负数,那么再进行思路1中的步骤。
Java代码:
package com.liuhao.acm.csdn; import java.io.BufferedInputStream; import java.util.Arrays; import java.util.Scanner; /** * @author liuhao * 绝对值最小 * 给你一个数组A[n],请你计算出ans=min(|A[i]+A[j]|)(0<=i,j<n). */ public class MinAbsoluteValue { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in)); while(sc.hasNext()){ int n = sc.nextInt(); int[] inputArr = new int[n]; for(int i=0; i<n;i++){ inputArr[i] = sc.nextInt(); } System.out.println(minAbsoluteValue(inputArr)); } sc.close(); // //测试数据 // int[] testArr1 = {1,2,3,4,23,45,67,4}; // int[] testArr2 = {-32,-34,-53,-354,-67}; // int[] testArr3 = {1,2,3,4,23,45,67,0,-32,-34,6,-53,-354,-67}; // int[] testArr4 = {1,2,3,4,23,45,67,-32,-34,6,-53,-354,-67}; // int[] testArr5 = {1,2,3,4,23,45,67,-32,-34,6,-53,-354,-68}; // // System.out.println(minAbsoluteValue(testArr1)); // System.out.println(minAbsoluteValue(testArr2)); // System.out.println(minAbsoluteValue(testArr3)); // System.out.println(minAbsoluteValue(testArr4)); // System.out.println(minAbsoluteValue(testArr5)); } private static int minAbsoluteValue(int[] inputArr){ Arrays.sort(inputArr); //若数组中包含0,则最小值肯定是0 if(Arrays.binarySearch(inputArr, 0) >= 0){ return 0; }else{ //若原数组全为正数,那么最小值就是正数组之中的最小值*2 if(-1 - Arrays.binarySearch(inputArr, 0) == 0){ return 2 * inputArr[0]; } //若全为负数,则最小值肯定是负数组之中最大值*-2 else if(-1 - Arrays.binarySearch(inputArr, 0) == inputArr.length){ return -2 * inputArr[inputArr.length-1]; } //既有正数又有负数 else{ int ans = Math.abs(2 * inputArr[0]); for(int i=0;i<inputArr.length;i++){ for(int j=i; j<inputArr.length;j++){ if(ans > Math.abs(inputArr[i] + inputArr[j])){ ans = Math.abs(inputArr[i] + inputArr[j]); } } } return ans; } } } }
代码获取地址:https://github.com/liuhao123/ACM
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。