请用时间复杂度最低的方法找出数组中数值差距最大的两个元素的差

[问答题]

请用时间复杂度最低的方法找出数组中数值差距最大的两个元素的差值？

红萝卜

设置两个临时变量t1，t2，然后遍历数组，t1始终保存较大值，t2保存较小值，遍历完毕，就能得到一个最大值t1，最小值t2。

是我想的太简单了，还是题就是这样？

发表于 2015-10-20 12:02:48 回复(6)

sichengLv

一次遍历，找出最大值max、最小值min，最大差值 = max - min，时间复杂度O(n)。

发表于 2018-04-01 14:51:55 回复(0)

十年一品温如言↗

冒泡算法，第一趟从前向后——倒数第一位最大的数，第二趟从倒数第二位向前——第一位为最小的数，最后一位减第一位。比较((n-1)+(n-2))次，比较O(2n)；最好情况换值0次（由小到大排好序的数组），最差情况换值((n-1)+(n-2))次，平均换值O(n)，复杂度O(3n)

发表于 2015-10-31 21:48:10 回复(0)

strange199704

用两次堆排序，第一次生成最大堆，得到最大值，第二次生成一个最小堆，得到最小值，时间复杂度是log(n)

发表于 2017-09-02 16:00:21 回复(1)

牛客2845338号

	public static void solution(int a[]) {
		int min = 0;
		int max = 0;
		for (int i = 1; i < a.length; i++) {
			if (a[i] > a[max])
				max = i;
			else if (a[i] < a[min])
				min = i;
		}
		System.out.println("the result is "+((a[max]-a[min])));
	}

发表于 2016-12-01 17:15:31 回复(0)

牛客707793号

用快速排序将数组排好序后，找出最小，最大值

发表于 2016-09-02 15:28:52 回复(0)

DanEmpress

public static int findNumber(int []arr){

if(arr==null||arr.length==0){

return 0;

}

int max=arr[0];

int min=arr[0];

for(int i=1;i<arr.length;i++){

if(arr[i]>max) max=arr[i];

if(arr[i]<min) min=arr[i];

}

return max=min;

}

发表于 2016-09-01 10:25:52 回复(0)

周星星_

//复杂度为O(n)
f(vector<int> v)
{
    int vmin,vmax;
    vmin=vmax=v[0];
    for(int i=1;i<v.size();i++)
    {
        if(v[i]>vmax) vmax=v[i];
        if(v[i]<vmin) vmin=v[i];
    }
    return abs(vmin-vmax);
}

发表于 2016-08-11 21:17:11 回复(0)

PatrickYang

	public static int findTheNumber(int[] array) {
		if(null == array || 0 == array.length) return 0;
		int min = array[0], max = array[0];
		for(int i = 1; i < array.length; i++) {
			if(array[i] > max) {
				max = array[i];
			}
			if(array[i] < min) {
				min = array[i];
			}
		}
		return max - min;
	}

发表于 2015-12-03 11:24:36 回复(0)