怎么用java代码实现这个功能,算法面试题目

天池番薯 发布于 2014/07/29 09:48
阅读 1K+
收藏 2

要从5个人中选取2个人作为礼仪,其中每个人的身高范围为160-190,要求2个人的身高差值最小(如果差值相同的话,选取其中最高的两人),以升序输出两个人的身高。

Smple input161 189 167 172 188 Sample outPut: 188 189

加载中
0
Tedd
Tedd

排个序,再比较...

只想到这种办法,没研究过算法,不清楚..

0
d
davidoo

升序排,算相邻之间的差值(后-前的正值),最小的靠后的,应该是要求的

import java.util.Arrays;


public class Test {
	
	public static int[] run(int[] input){
		if(input == null || input.length <=1){
			return input;
		}
		//排序
		int temp = 0;
		for(int i= input.length-1;i>=1;i--){
			for(int j= 0;j<=i-1;j++){
				if(input[j] > input[j+1]){
					temp = input[j];
					input[j] = input[j+1];
					input[j+1] = temp;
				}
			}
		}
		//算差值
		int index =0,min=Integer.MAX_VALUE;
		for(int i= 0;i<=input.length-2;i++){
			if(input[i+1]-input[i]<=min){
				index = i;
				min = input[i+1]-input[i];
			}
		}
		
		return Arrays.copyOfRange(input, index, index+2);
	}
	public static void main(String[] args) {
		int[] input =new int[]{161,189,167,172,188};
		int[] output = run(Arrays.copyOf(input, input.length));
		for(int i :output){
			System.out.println(i);
		}
	}

}



d
davidoo
回复 @thomas2 : 不排序,直接相互比较,记录差值最小的最大的2者,见下面回复
天池番薯
天池番薯
可以加上注释,和想法不, 其实感觉还可以效率更高一些, 你觉得呢?
0
星爷
星爷
恩,首先排序,在计算两个值之间的差值作比较即可
0
RegnoiX
RegnoiX

直接比 不用排序吧


0
一只小桃子
一只小桃子
两层for循环
0
d
davidoo

2层for循环的实现:直接相互比较,记录差值最小的最大2个数

import java.util.Arrays;


public class Test {
	
	public static int[] run(int[] input){
		if(input == null || input.length <=1){
			return input;
		}
		int temp = 0;//临时比较值 
		int index1=0;//记录比较的一方的位置,也可以直接记录值
		int index2=1;//比较的另一方的位置
		int min=Integer.MAX_VALUE;//当前最小的差值
		int length = input.length;
		//两个之间相互比较,双层循环
		for(int i= 0;i<= length - 2 ;i++){
			for(int j= i+1;j<= length -1;j++){
				temp = Math.abs(input[i]-input[j]);//差值的绝对值
				if(temp < min){//如果差值更小
					min = temp;
					index1 = i;
					index2 = j;
				}else if(temp == min){//如果差值相等
					if(input[i] + input[j]  > input[index1] + input[index2] ){//如果和更大
						index1 = i;
						index2 = j;
					}
				}
			}
		}
		//设置返回值
		int[] rtn = new int[2];//返回值
		rtn[0] = input[index1] < input[index2]?input[index1]:input[index2];
		rtn[1] =  input[index2] > input[index1]?input[index2]:input[index1];
		return rtn;
	}
	public static void main(String[] args) {
		int[] input =new int[]{161,189,167,172,188};
		int[] output = run(Arrays.copyOf(input, input.length));
		for(int i :output){
			System.out.println(i);
		}
	}

}



傅一
傅一
同意这种做法,这种做法效率高。
天池番薯
天池番薯
不错,这个效率不错,比之前高很多
0
郭大侠
郭大侠
如果5、2变成了可变参数,想了30秒不知怎么实现。
0
藍色的海
藍色的海

这些问题项目好少用到 学点实用的更好

天池番薯
天池番薯
我觉得会有这样的情况,
0
excepiton
excepiton

进行一次堆排序就知道答案了。


0
excepiton
excepiton

下面是用堆排序进行的一次比较。

public class App {
	public static void main(String[] args) {
		int[] array = { 161,190, 189, 167, 172, 188 };
		int pair1 = 0;
		int pair2 = 0;
		int delta = Integer.MAX_VALUE;

		head(array, array.length);
		for (int i = array.length - 1; i > 0; i--) {
			head(array, i);
			int sub = array[i] - array[i - 1];
			if (sub < delta) {
				pair1 = array[i];
				pair2 = array[i - 1];
				delta = sub;
			}
		}
		System.out.println("delta is " + delta + ". pair : <" + pair2 + ","
				+ pair1 + ">");
	}

	/**
	 * 堆排序,把数组建立大顶堆后,把堆顶元素放到array[size-1]
	 * @param array
	 * @param size
	 */
	public static void head(int[] array, int size) {
		if (size == 1) {
			return;
		}
		int length = size;
		int t = (length - 1) / 2;
		for (int i = t; i >= 0; i--) {
			heapify(array, i, length);
		}
		swap(array, 0, size - 1);
	}

	public static void heapify(int[] array, int i, int size) {
		int l = ((i * 2) + 1);
		int r = l + 1;
		int min = i;
		if (l < size && array[l] > array[min]) {
			min = l;
		}
		if (r < size && array[r] > array[min]) {
			min = r;
		}
		if (min != i) {
			swap(array, min, i);
			if (min < size - 1) {
				heapify(array, min, size);
			}
		}
	}

	public static void swap(int[] array, int i, int j) {
		array[i] ^= array[j];
		array[j] ^= array[i];
		array[i] ^= array[j];
	}
}



返回顶部
顶部