首页 > 代码库 > 绝对值最小--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