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

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

Smple input161 189 167 172 188 Sample outPut: 188 189

举报
共有11个答案 最后回答: 4年前

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

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);
		}
	}

}



--- 共有 2 条评论 ---
davidoo回复 @thomas2 : 不排序,直接相互比较,记录差值最小的最大的2者,见下面回复 4年前 回复
vr和ar加油努力可以加上注释,和想法不, 其实感觉还可以效率更高一些, 你觉得呢? 4年前 回复

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);
		}
	}

}



--- 共有 2 条评论 ---
傅一同意这种做法,这种做法效率高。 4年前 回复
vr和ar加油努力不错,这个效率不错,比之前高很多 4年前 回复

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

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];
	}
}



顶部