首页 > 试题广场 >

相邻最大差值

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

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

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

测试样例:
[9,3,1,10],4
返回:6
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)
我这个排序很简单,调用的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)
冒泡排序,然后求出最大差值;
发表于 2018-09-08 18:17:16 回复(0)
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)
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)
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)
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)
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)