首页 > 试题广场 >

数组排序之后相邻数的最大差值

[编程题]数组排序之后相邻数的最大差值
  • 热度指数：3182 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个整形数组arr，返回排序后相邻两数的最大差值
arr = [9, 3, 1, 10]。如果排序，结果为[1, 3, 9, 10]，9和3的差为最大差值，故返回6。
arr = [5, 5, 5, 5]。返回0。
[要求]
时间复杂度为，空间复杂度为


输入描述:
第一行一个整数N。表示数组长度。
接下来N个整数表示数组内的元素


输出描述:
输出一个整数表示答案
示例1

输入

4
9 3 1 10

输出

6
示例2

输入

4
5 5 5 5

输出

0

备注:

算法知识视频讲解
添加回答
Java
pein531头像 pein531
基数排序，空间复杂度和时间复杂度都是O(N)，排完序后再遍历一遍数组计算最大的相邻差值，复杂度仍然是O(N)。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(strArr[i]);
            max = Math.max(max, arr[i]);
        }
        int maxBits = getMaxBits(max);
        radixSort(arr, maxBits);
        int maxDiff = -1;
        for(int i = 1; i < n; i++) maxDiff = Math.max(arr[i] - arr[i - 1], maxDiff);
        System.out.println(maxDiff);
    }
    
    // 基数排序
    private static void radixSort(int[] arr, int maxBits) {
        final int radix = 10;
        int n = arr.length;
        int[] bucket = new int[n];
        for(int d = 1; d <= maxBits; d++){
            int[] count = new int[radix];
            // 按倒数第d位计算词频数组
            for(int i = 0; i < n; i++){
                int digit = getDigits(arr[i], d);
                count[digit] ++;
            }
            // 计算词频数组的前缀和
            for(int i = 1; i < radix; i++) count[i] += count[i - 1];
            // 按数位入桶（通过词频数组前缀和就可以知道某个数要进入哪个桶）
            for(int i = arr.length - 1; i >= 0; i--){
                int j = getDigits(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j] --;
            }
            for(int i = 0; i < n; i++) arr[i] = bucket[i];       // 出桶
        }
    }
    
    // 获得数的十进制位数
    private static int getMaxBits(int num) {
        int bits = 0;
        while(num != 0){
            bits ++;
            num /= 10;
        }
        return bits;
    }
    
    // 获得一个数倒数第d位的数字
    private static int getDigits(int num, int d) {
        int res = 0;
        for(int i = 1; i <= d; i++){
            res = num % 10;
            num /= 10;
        }
        return res;
    }
}

发表于 2021-11-19 20:54:28 回复(0)
Java
小星教授头像 小星教授 
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int MAX =Integer.MIN_VALUE;
		int MIN = Integer.MAX_VALUE;
		int n = scanner.nextInt();
        int[] arr = new int[n];
        
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
            MAX = Math.max(arr[i], MAX);
            MIN = Math.min(arr[i], MIN);
        }
        
       
        int max[] = new int[n+1];
        int min[] = new int[n+1];
        boolean hasNum[] = new boolean[n+1];
        for(int i=0;i<n+1;i++) {
        	max[i] = Integer.MIN_VALUE;
        	min[i] = Integer.MAX_VALUE;
        }
        
        for(int i=0;i<n;i++) {
        	int bucketNum = bucket(arr[i], n, MIN, MAX);
        	max[bucketNum] = Math.max(max[bucketNum], arr[i]);
        	min[bucketNum] = Math.min(min[bucketNum], arr[i]);
        	hasNum[bucketNum] = true;
        }
       
        int res = 0;
        int lastMax = max[0];
        for(int i = 1;i<n+1;i++) {
        	if(hasNum[i]) {
        		res = Math.max(res,min[i]-lastMax );
        		lastMax = max[i];
        	}
        }
        
        System.out.println(res);
		
	}
	public static int bucket(long num,long len,long min, long max){
        return (int) ((num-min)*len/(max-min));
    }
}

发表于 2019-10-25 11:17:38 回复(0)
提交观点

问题信息

排序
上传者：小小
难度：
2条回答 6475浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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