找一个数组中绝对值和最小的三个元素

文章目录

1. 1. 题目
2. 2. 解析
3. 3. 代码
4. 4. 参考

题目

找一个数组中绝对值和最小的三个元素

解析

暴力的方法是O(n^3)，肯定还存在其他更加优的方法

1. 将数组升序排序
2. 固定一个数字，然后从两端开始找，如果sum<0 则left++ 否则right— 同时记录最小的minSum

   注意，两端向中间找的时候如果遇到当前固定的数字需要跳过

代码

public static void minAbsThreeNumber(int[] a){

	
	int left=0,mid=0,right=0;
	int mas=Integer.MAX_VALUE;//min abs sum
	
	Arrays.sort(a);//这里使用了快速排序  会破坏原有数组 不过由于本题重点不在这里 所以也就不需要考虑了
	
	//mas==0 的时候已经是最小的sum了，如果出现这种情况可以直接停止
	for(int k=0;k<a.length&&mas!=0;k++)
	{
		//固定的那个数字为k
		for(int i=0,j=k-1;i<j && mas!=0;)
		{
			//两个continue操作是避免重复使用了k
			if(i==k)
			{
				i++;
				continue;
			}
			
			if(j==k)
			{
				j--;
				continue;
			}
			
			//更新最小的abs(sum)
			int sum=a[i]+a[k]+a[j];
			if(Math.abs(sum)<mas)
			{
				mas=Math.abs(sum);
				left=i;
				mid=k;
				right=j;
			}
			
			if(sum<0)
			{
				i++;//增加sum
			}else{
				j--;//减少sum
			}
			
		}
	}
	
	System.out.println(String.format("min abs sum:%s=(%s)+(%s)+(%s)",mas,a[left],a[mid],a[right]));
}

测试

public static void main(String[] args) {
	int a[]={-9,9,0,-2,3};
	int b[]={-99,66,0,2,3};
	minAbsThreeNumber(b);
	
}

输出结果为

min abs sum:5=(0)+(3)+(2)

它的最终复杂度是O(n^2)，还是有所提升的

参考

http://blog.csdn.net/deutschester/article/details/5981503

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。