首页 > 试题广场 >

相邻最大差值

[编程题]相邻最大差值
  • 热度指数：17412 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。

给定一个整数数组A和数组的大小n，请返回最大差值。保证数组元素个数大于等于2小于等于500。

测试样例： 
[9,3,1,10],4
返回：6
算法知识视频讲解
添加回答
Java
hitcs头像 hitcs 
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//删除输入字符串中的‘【’和‘】’的函数；
    public static String delete(String a) {
        String b="";
        for(int i=0;i<a.length();i++) {
            if(a.charAt(i)!='['&&a.charAt(i)!=']') {
                b+=a.charAt(i);
            }
        }
        return b;
    }
    public static void main(String[] args) {
     Scanner in=new Scanner(System.in);
     while(in.hasNext()) {
      String s=in.next();
      String t=delete(s);
//把删除‘【’和‘】’后的字符串以‘，’为间隔储存在String数组中
      String []arr=t.split(",");
//并将其转化为int储存在数组中，注意不要将最后一位表示题目所指数组长度的数字存入其中
      int []num=new int[arr.length-1];
      for(int i=0;i<num.length;i++) {
          num[i]=Integer.parseInt(arr[i]);
      }
//int类型数组自动排序
     Arrays.sort(num); 
//找出相差最大的相邻元素的差

    int sum=0;
    int i=1;
    while(i<num.length) {
        int sum1=num[i]-num[i-1];
        if(sum1>sum) {
            sum=sum1;
            i++;
        }
        else i++;
    }
    System.out.println(sum);
    }
}
}
发表于 2019-03-02 11:25:53 回复(0)
Java
失心失人头像 失心失人 
我这个排序很简单，调用的Array的sort方法，而sort方法内部是快速排序，其时间效率很高。所以关键在于如何找出最大差值，其实也比较简单，就是用max来存储最大值。
int max=0;
        Arrays.sort(A);
        for (int i=0;i<A.length;i++){
            if(i+1< n){
                if(max<(A[i+1]-A[i])){
                    max=(A[i+1]-A[i]);
                }
           }
        }
        return max;
发表于 2019-01-12 13:42:03 回复(0)
Java
圣诞节的安徒生头像 圣诞节的安徒生
冒泡排序，然后求出最大差值；
发表于 2018-09-08 18:17:16 回复(0)
Java
倦意的过客头像 倦意的过客 
import java.util.*;
//这样也行吧
public class MaxDivision {
    public int findMaxDivision(int[] A, int n) {
        // write code here
        Arrays.sort(A);
        int[] B = new int[n-1];
        for(int i=0;i<n-1;i++){
            B[i] = A[i+1]-A[i];
        }
        Arrays.sort(B);
        return B[n-2];
    }
}

发表于 2018-07-20 17:05:59 回复(0)
Java
010101010101头像 010101010101
import java.util.*;
import java.util.Arrays;
public class MaxDivision {
    public int findMaxDivision(int[] A, int n) {
        // write code here
         Arrays.sort(A,0,n);
        
        int max1=0;
        int d=0;
            for(int i=0;i<n-1;i++)
            {
                d=A[i+1]-A[i];
                if(max1<d)
                    max1=d;
            }
        return max1;
    }
}
发表于 2017-11-08 22:15:44 回复(0)
Java
詆調壹點头像 詆調壹點 
import java.util.*;

public class MaxDivision {
    public int findMaxDivision(int[] A, int n) {
        // 计数排序,时间复杂度O(max-min+1),空间复杂度O(max-min+1),达不到O(n)
		int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
		for (int i = 0; i < A.length; i ++) {
			max = max > A[i] ? max : A[i];
			min = min < A[i] ? min : A[i];
		}
		boolean[] flag = new boolean[max - min + 1];
		for (int i = 0; i < n; i ++) {
			flag[A[i] - min] = true;
		}
		int res = Integer.MIN_VALUE;
		int cur = 0, pre = 0;
		while ( ! flag[pre]) {
			cur ++;
			pre ++;
		}
		for (; cur < flag.length; cur ++) {
			if(flag[cur]) {
				res = res > cur - pre ? res : cur - pre;
				pre = cur;
			}
		}
		return res;
	}
}
编辑于 2017-03-11 00:09:32 回复(0)
Java
金宝子头像 金宝子 
import java.util.*;

public class MaxDivision {
    public int findMaxDivision(int[] A, int n) {
        // write code here
        int max = 0;
        Arrays.sort(A);
        for(int i = 0; i < n-1; i++){
            if(A[i+1] - A[i] > max){
                max = A[i+1] - A[i];
            }
        }
        return max;
    }
}

发表于 2016-08-18 15:18:33 回复(0)
Java
小开心头像 小开心
import java.util.*;

public class MaxDivision {
    public int findMaxDivision(int[] A, int n) {
        int max = A[0];
        int min = A[0];
        for(int i=1;i<n;i++){
            if(A[i]>=max){
                max = A[i];
            }
            if(A[i]<=min){
                min = A[i];
            }
        }
        if(max == min){
            return 0;
        }
        int bolt = (max-min)/n;
        int[][] boltArray = new int[n+1][2];
        boltArray[n][0] = max;
        Map<String,String> flagMap = new HashMap<String,String>();
        for(int i=0;i<n;i++){
            int m = (A[i]-min)*n/(max-min);
            if(!flagMap.containsKey(String.valueOf(m))){
                boltArray[m][0] = A[i];
                boltArray[m][1] = A[i];
                flagMap.put(String.valueOf(m),"true");
            }else{
                if(A[i]<=boltArray[m][0]){
                    boltArray[m][0] = A[i];
                }
                if(A[i]>=boltArray[m][1]){
                    boltArray[m][1] = A[i];
                }
            }
            
        }
        int maxdivision = 0;
        int count = 0;
        for(int i=0;i<=n;i++){
            if(i==0 && boltArray[i][0] == 0 && boltArray[i][1] == 0){
                int temp = boltArray[1][0] - boltArray[0][1];
                if(temp>=maxdivision){
                        maxdivision = temp;
                }
                
            }
            if(i!=0 && boltArray[i][0] == 0 && boltArray[i][1] == 0){
                count++;
            }else{
                if(count>0){
            int temp = boltArray[i][0] - boltArray[i-count-1][1];
                    if(temp>=maxdivision){
                        maxdivision = temp;
                    }
                    count = 0;
            }
            }
        }
        return maxdivision;
    }
} 
发表于 2016-06-28 23:22:38 回复(0)
提交观点

问题信息

编程基础 数组 查找
来自：经典算法题精讲（六）-...
难度：
8条回答 50997浏览

热门推荐

通过挑战的用户

查看代码

相关试题

相邻最大差值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号