给定一个整形数组arr，返回排序后相邻两数的最大差值
arr = [9, 3, 1, 10]。如果排序，结果为[1, 3, 9, 10]，9和3的差为最大差值，故返回6。
arr = [5, 5, 5, 5]。返回0。
[要求]
时间复杂度为)
，空间复杂度为
[编程题]数组排序之后相邻数的最大差值
左神书上的思路，使用了类似于桶排序的思想，时间复杂度O(n).
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int [] arr = new int[n];
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i=0;i<n;i++){
arr[i] = scanner.nextInt();
min = Math.min(min,arr[i]);
max = Math.max(max,arr[i]);
}
if(min == max){
System.out.println(0);
}else{
boolean [] hasNum = new boolean[n+1];
int [] maxs = new int[n+1];
int [] mins = new int[n+1];
int bid = 0;
for(int i=0;i<n;i++){
bid = bucket(arr[i],n,min,max);
mins[bid] = hasNum[bid]?Math.min(mins[bid],arr[i]):arr[i];
maxs[bid] = hasNum[bid]?Math.max(maxs[bid],arr[i]):arr[i];
hasNum[bid] = true;
}
int res = 0;
int lastMax = maxs[0];
for(int i=1;i<=n;i++){
if(hasNum[i]){
res = Math.max(res,mins[i]-lastMax);
lastMax = maxs[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-08-15 16:15:07
回复(0)
更多回答
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, Min=INT_MAX, Max=0, L=0, l[1000000]={0}, r[1000000]={0};
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
Max = max(Max, a[i]);
Min = min(Min, a[i]);
}
int t = (Max-Min)/(n-1)+1;
for(int i=0;i<n;i++){
int b = (a[i]-Min)/t;
if(l[b]==0 || l[b]>a[i])
l[b] = a[i];
if(r[b]==0 || r[b]<a[i])
r[b] = a[i];
}
int i=0, j=1;
while(i<j){
while(j<n && l[j]==0)
j++;
if(j==n)
break;
if(l[j]-r[i]>L)
L = l[j] - r[i];
i = j;
j++;
}
cout<<L<<endl;
return 0;
}
发表于 2020-03-02 00:44:45
回复(0)
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> arr(n, 0);
for (int i=0; i<n; i++) cin >> arr[i];
int min = INT_MAX, max = INT_MIN;
for (int num : arr)
{
min = min < num ? min : num;
max = max > num ? max : num;
}
if (min == max)
{
cout << 0 << endl;
return 0;
}
vector<bool> flag(n+1, false);
vector<int> mins(n+1, INT_MAX);
vector<int> maxs(n+1, INT_MIN);
for (int i=0; i<n; i++)
{
int mid = (int)((long)arr[i] - (long)min)*(long)n / ((long)max - (long)min);
mins[mid] = flag[mid] ? (arr[i] < mins[mid] ? arr[i] : mins[mid]) : arr[i];
maxs[mid] = flag[mid] ? (arr[i] > maxs[mid] ? arr[i] : maxs[mid]) : arr[i];
flag[mid] = true;
}
int res = 0;
int lastLargest = maxs[0];
for (int i=1; i<=n; i++)
{
if (flag[i])
{
res = res > mins[i] - lastLargest ? res : mins[i] - lastLargest;
lastLargest = maxs[i];
}
}
cout << res << endl;
return 0;
}
发表于 2019-10-11 23:16:25
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>res(n);
for(int i=0;i<n;i++)
cin>>res[i];
if (res.size() < 2)
{
cout<<0<<endl;
return 0;
}
int mi = INT_MAX, ma = INT_MIN;
for (int i = 0; i < n; i++){
mi = min(mi, res[i]);
ma = max(ma, res[i]);
}
if (mi == ma)
{
cout<<0<<endl;
return 0;
}
vector<bool>hasnum(n + 1);
vector<int>mas(n + 1), mis(n + 1);
int bid = 0;
for (int i = 0; i < n; i++){
bid = (int)(((long)res[i] - (long)mi)*(long)n / ((long)ma - (long)mi));
mis[bid] = hasnum[bid] ? min(mis[bid], res[i]) : res[i];
mas[bid] = hasnum[bid] ? max(mas[bid], res[i]) : res[i];
hasnum[bid] = true;
}
int ans = 0, lastma = 0, i = 0;
while (i <= n){
if (hasnum[i++]){
lastma = mas[i - 1];
break;
}
}
for (; i <= n; i++){
if (hasnum[i]){
ans = max(ans, mis[i] - lastma);
lastma = mas[i];
}
}
cout<<ans<<endl;
return 0;
}
发表于 2019-08-30 21:51:19
回复(0)
//虽然是直接用的数组自带的排序算法，但是结果的时间和内存都通过了
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums); // 使用排序算法对数组进行排序
int maxGap = 0;
for (int i = 1; i < nums.length; i++) {
maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
}
return maxGap;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
System.out.println(maxGap(arr));
}
}
发表于 2023-06-30 17:53:45
回复(0)
基数排序，空间复杂度和时间复杂度都是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)
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)
import java.util.*;
import java.util.stream.Collectors;
public class Main26 {
// 给定一个整形数组arr，返回排序后相邻两数的最大差值
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int length = scan.nextInt();
scan.nextLine();
String str = scan.nextLine();
str = str.substring(1, str.length()-1);
List<Integer> list = Arrays.stream(str.split(" ")).map(Integer::parseInt).sorted().collect(Collectors.toList());
int max = 0;
for(int i = list.size()-1; i > 0; i--){
int diff = list.get(i) - list.get(i-1);
max = Math.max(max, diff);
}
System.out.println(max);
}
}
编辑于 2024-03-07 14:58:26
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(getMaxDiff(arr));
sc.close();
}
/*
利用了桶排序的思想，做到时间空间复杂度皆为O(N)
首先准备n+1个桶，然后把n个数分别装进n+1个桶里，桶的排号分别是0~n
分别可装的区间为：0号桶装[min, (max-min)/n],
1号桶装[(max-min)/n, 2*(max-min)/n]....
也就是说每个桶可覆盖的范围是(max-min)/n.
因为只有n个数，却有n+1个桶，那么至少有一个桶是空的，所以排序后相邻的两数最大和，
必来自于某个空桶前一个非空桶中最大数，和此空桶后一个非空桶中最小数，的差！
所以我们只需要记录每个桶中的最大值和最小值即可。
*/
public static int getMaxDiff(int[] arr) {
if (arr == null || arr.length < 2)
return 0;
int len = arr.length;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
min = Math.min(min, arr[i]);
max = Math.max(max, arr[i]);
}
if (max == min)
return 0;
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len+1];
int[] mins = new int[len+1];
int res = 0;
int pre = maxs[0];
for (int i = 0; i < len; i++) {
int index = getIndex(arr[i], arr.length, min, max);
maxs[index] = hasNum[index] ? Math.max(maxs[index], arr[i]) : arr[i];
mins[index] = hasNum[index] ? Math.min(mins[index], arr[i]) : arr[i];
hasNum[index] = true;
}
for (int i = 0; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - pre);
pre = maxs[i];
}
}
return res;
}
//返回一个位置，代表应该把val放入几号桶中
public static int getIndex(long val, long n, long min, long max) {
return (int)((val - min) * n / (max - min));
}
}
发表于 2021-08-26 21:37:19
回复(0)
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <bits/stdc++.h>
using namespace std;
int bucket(long num,long len,long mindata,long maxdata)
{
return (int)((num-mindata)*len/(maxdata-mindata));
}
int main()
{
int n;
cin>>n;
vector<int> data(n);
int mindata=INT_MAX;
int maxdata=INT_MIN;
for(int i=0;i<n;i++)
{
cin>>data[i];
mindata=min(data[i],mindata);
maxdata=max(data[i],maxdata);
}
if(data.empty()||n<2)
{
return 0;
}
if(mindata==maxdata)
return 0;
vector<bool> booldata(n+1);
vector<int>mins(n+1);
vector<int>maxs(n+1);
int bid=0;
for(int i=0;i<n;i++)
{
bid=bucket(data[i],n,mindata,maxdata);
mins[bid]=booldata[bid]?min(mins[bid],data[i]):data[i];
maxs[bid]=booldata[bid]?max(maxs[bid],data[i]):data[i];
booldata[bid]=true;
}
int res=0;
int lastmax=maxs[0];
int i=1;
for(;i<=n;i++)
{
if(booldata[i])
{
res=max(res,mins[i]-lastmax);
lastmax=maxs[i];
}
}
cout<<res<<endl;
return 0;
}
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <bits/stdc++.h>
using namespace std;
int bucket(long num,long len,long mindata,long maxdata)
{
return (int)((num-mindata)*len/(maxdata-mindata));
}
int main()
{
int n;
cin>>n;
vector<int> data(n);
int mindata=INT_MAX;
int maxdata=INT_MIN;
for(int i=0;i<n;i++)
{
cin>>data[i];
mindata=min(data[i],mindata);
maxdata=max(data[i],maxdata);
}
if(data.empty()||n<2)
{
return 0;
}
if(mindata==maxdata)
return 0;
vector<bool> booldata(n+1);
vector<int>mins(n+1);
vector<int>maxs(n+1);
int bid=0;
for(int i=0;i<n;i++)
{
bid=bucket(data[i],n,mindata,maxdata);
mins[bid]=booldata[bid]?min(mins[bid],data[i]):data[i];
maxs[bid]=booldata[bid]?max(maxs[bid],data[i]):data[i];
booldata[bid]=true;
}
int res=0;
int lastmax=maxs[0];
int i=1;
for(;i<=n;i++)
{
if(booldata[i])
{
res=max(res,mins[i]-lastmax);
lastmax=maxs[i];
}
}
cout<<res<<endl;
return 0;
}
编辑于 2021-01-29 15:47:05
回复(0)
#include<iostream>
using namespace std;
const int N = 1e6+3;
typedef long long ll;
int a[N];
bool hasNum[N];
int max_arr[N],min_arr[N];
int index(ll mi,ll ma,ll idx) {
return (idx-mi)*(N-1) / (ma-mi);
}
int result(int n) {
if(n==0|| n<2) return 0;
int ma = -99,mi = 1e9+7;
for(int i=0;i<n;++i) ma = max(ma,a[i]),mi = min(mi, a[i]);
for(int i=0;i<n;++i) {
int idx = index(mi,ma,a[i]);
max_arr[idx] = hasNum[idx]? max(max_arr[idx],a[i]): a[i];
min_arr[idx] = hasNum[idx]? min(min_arr[idx],a[i]): a[i];
hasNum[idx] = true;
}
int begin=0,lastMax = 0;
for(int i=0;i<n;++i) {
if(hasNum[i]) {
begin = i;
lastMax = max_arr[i];
break;
}
}
int dx = 0;
for(int i=begin;i<n;++i) {
if(hasNum[i])dx = max(dx, min_arr[i]-lastMax), lastMax = max_arr[i];
}
return dx;
}
int main() {
int n;cin>>n;
for(int i=0;i<n;++i) cin>>a[i];
cout << result(n) << endl;
}
发表于 2021-01-28 20:42:50
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct buket {
int max;
int min;
bool has_num;
};
int main(void)
{
int N, num;
cin >> N;
vector<int> vc;
for (int i = 0; i < N; i++) {
cin >> num;
vc.push_back(num);
}
int max_num = *max_element(vc.begin(), vc.end());
int min_num = *min_element(vc.begin(), vc.end());
vector<buket> bukets(vc.size() + 1);
//bukets[0].min = min_num;
//bukets[bukets.size() - 1].max = max_num;
for (int i = 0; i < vc.size(); i++) {
int j = (vc[i] - min_num) * vc.size()/ (max_num - min_num) ;
bukets[j].min = bukets[j].has_num ? min(bukets[j].min, vc[i]) : vc[i];
bukets[j].max = bukets[j].has_num ? max(bukets[j].max, vc[i]) : vc[i];
bukets[j].has_num = true;
}
int last_max = bukets[0].max;
int res = 0;
for (int i = 1; i < bukets.size(); i++) {
res = bukets[i].has_num ? max(bukets[i].min - last_max, res) : res;
last_max = bukets[i].has_num ? bukets[i].max : last_max;
}
cout << res;
return 0;
}
发表于 2020-02-05 11:13:51
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-10 17:41:48
-
2023-02-21 17:59:24
-
2023-02-21 10:07:23 -
2023-02-18 13:22:22 -
2023-01-11 23:03:30
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
