当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-求数组中两两元素之差绝对值最小值

发表于: 2012-03-12   作者:bylijinnan   来源:转载   浏览次数:
摘要: import java.util.Arrays; public class MinDifference { /** * 题目:求数组中两两元素之差绝对值最小值 solution 1.sort the data array.Find the min difference between two adjacent element. solution 2. 设这个整数数组是
import java.util.Arrays;

public class MinDifference {

	/**
	 * 题目:求数组中两两元素之差绝对值最小值
solution 1.sort the data array.Find the min difference between two adjacent element.
solution 2.
设这个整数数组是a1,a2,...,an
构造数组B=(b1,b2,...,bn-1) 
b1 = a1-a2, 
b2 = a2-a3, 
b3 = a3-a4, 
... 
bn-1 = an-1 - an 

那么原数组中,任意两整数之差ai-aj(1 <=i,j <=n)可以表示成 
B中第i个到第j-1个元素的连续求和 

例如b2+b3+b4 = (a2-a3) + (a3-a4) + (a4-a5) = a2-a5 

O(n)构造出B序列后 

用类似“最大子段和”算法求“最小绝对值子段和”

但是,如何求得“最小绝对值子段和”?我没有想出来。。。
	 */
	public static void main(String[] args) {

		int[] data={1,2,4,8,15,20,18,-3,11};
		int min=minDifference(data);
		System.out.println(min);
	}

	public static int minDifference(int[] data){
		if(data==null||data.length==0){
			return Integer.MIN_VALUE;
		}
		sort(data,0,data.length-1);
		int len=data.length;
		int[] diff=new int[len-1];
		for(int i=0;i<len-1;i++){
			diff[i]=data[i+1]-data[i];
		}
		//System.out.println(Arrays.toString(diff));
		return min(diff);
	}
	public static int min(int[] diff){
		if(diff==null||diff.length==0){
			return Integer.MIN_VALUE;
		}
		int min=diff[0];
		for(int i=0,len=diff.length;i<len;i++){
			//not necessary,since 'int[] data' is sorted,so 'int[] diff' is progressively increased.
			//int tmp=diff[i]>0?diff[i]:(-diff[i]);
			if(min>diff[i]){
				min=diff[i];
			}
		}
		return min;
	}
	
	//QuickSort.Of course we can use Arrays.sort(),but I write it for practice.
	public static void sort(int[] x,int s,int e){
		if(s>=e){
			return;
		}
		int i=s;
		int j=e;
		boolean flag=false;
		while(i!=j){
			if(x[i]>x[j]){
				swap(x,i,j);
				flag=!flag;
			}
			if(flag){
				i++;
			}else{
				j--;
			}
		}
		sort(x,s,i-1);
		sort(x,j+1,e);
	}
	
	public static void swap(int[] x,int i,int j){
		int tmp=x[i];
		x[i]=x[j];
		x[j]=tmp;
	}
}

java-求数组中两两元素之差绝对值最小值

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
  这两天去 牛客网 混了下,遇到的几道题都很有意思,尤其是今晚这道,比赛时不会做,后来看了别
此题有2种变形: 1、不能修改node结构,要求时间O(N). 2、可以修改node结构,要求时间O(logN). 这里
寻找一个数组里的最大值和最小值 法一: 分别遍历一遍,次数O(2*N); 法二: 根据书上的讲述, 法三
在java 中如何获取元素在数组中的位置呢? (1) /*** * Get location of element in a array * @param
现在有这样一个问题: 首先定义一个大小为20的整型数组,就好像这样-- int a[20], 之后,根据需要存
在java 中如何获取元素在数组中的位置呢? (1) /*** * Get location of element in a array * @param
在java 中如何获取元素在数组中的位置呢? (1) /*** * Get location of element in a array * @param
在java 中如何获取元素在数组中的位置呢? (1) /*** * Get location of element in a array * @param
蓄水池抽样(Reservoir Sampling) 相关证明可看这个链接: http://www.cnblogs.com/HappyAngel/arch
题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号