给定一个整形数组arr,返回排序后相邻两数的最大差值
arr = [9, 3, 1, 10]。如果排序,结果为[1, 3, 9, 10],9和3的差为最大差值,故返回6。
arr = [5, 5, 5, 5]。返回0。
[要求]
时间复杂度为,空间复杂度为
第一行一个整数N。表示数组长度。
接下来N个整数表示数组内的元素
输出一个整数表示答案
4 9 3 1 10
6
4 5 5 5 5
0
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)); } }
#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; }
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)); } }
#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; }
#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; }
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; } }
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); } }
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)); } }
#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; }
#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; }