[编程题]有趣的数字
- 热度指数：36005 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？
输入描述:
输入包含多组测试数据。
对于每组测试数据：
N - 本组测试数据有n个数
a1,a2...an - 需要计算的数据
保证:
1<=N<=100000,0<=ai<=INT_MAX.
输出描述:
对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
示例1
输入
6 45 12 45 32 5 6
输出
1 2
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void result(vector<int>&a, int n);
int main()
{
int num;
while (cin >> num)
{
int temp;
vector<int>data;
for (int i = 0; i < num; ++i)
{
cin >> temp;
data.push_back(temp);
}
result(data, num);
}
return 0;
}
void result(vector<int>&a, int n)
{
if (n > 1)
{
sort(a.begin(), a.end());
int m1 = 1;
int m2 = 1;
for (int i = 0; i < n-1; ++i)
{
if (a[i + 1] != a[i])
break;
++m1;
}
for (int i = n - 1; i > 0; --i)
{
if (a[i - 1] != a[i])
break;
++m2;
}
int max = m1*m2;
int min_temp = a[1] - a[0];
int min = 0;
for (int i = 2; i < n; ++i)
if (a[i] - a[i - 1] < min_temp)
min_temp = a[i] - a[i - 1];
if (min_temp == 0)
{
for (int i = 1; i < n; ++i)
{
int j = i - 1;
while (j >= 0 && a[j] == a[i])
{
++min;
--j;
}
}
}
else
{
for (int i = 1; i < n; ++i)
if (a[i] - a[i - 1] == min_temp)
++min;
}
cout << min << ' ' << max << endl;
}
}
发表于 2016-07-12 22:16:47
回复(10)
我的思路是先用快排，然后对有序数组分别求差值最大的对数和差值最小的对数。
快排之后，如果数组为常数数组，即最大值=最小值，则结果已经出来了。否则，进行下面的操作，其中：
1. 差值最大的好求，看有序数组有几个最小值和几个最大值，相乘即可。
2.
差值最小的，由于是有序数组，必定是相邻的差值较小，故由快排后的有序数组生成差值数组（即相邻的两两相减）。如果差值数组中0，则查看差值数组中连续0的组数，可以由排列组合知识计算总的差值最小的对数；如果差值数组中没有0，则只需计算差值数组中有多少个最小值即可。注：差值数组必定都是非负数。
3. 空间复杂度较大，需要一些辅助数组。
4. 时间复杂度：快排O(NlogN)，求差值最大O(N)，求差值最小O(N)，所以最终的时间复杂度为O(NlogN)。
编辑于 2016-08-10 20:50:03
回复(2)
思路：
- 先排序
- 求差为最小值的对数
- 先求最小值minVal
- 若存在重复的元素：差为0，双重循环求差为0的对数，即得到minCount
- 若不存在重复的元素：最小值只出现在相邻元素间，循环一次即可得到minCount
- 求差为最大值的对数
- 若全部元素都相等，利用排列组合的知识：maxCount=x*(x-1)/2
- 若不是全部元素都相等：maxCount=最小元素的个数*最大元素的个数
注意：千万不要忽略重复元素的情况！比如：3 3 3 3，最大值对是6对！而不是3对，更不是12对！
所用数据结构： vector
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int num,i,j;
while(cin>>num)//读入元素的总个数
{
if(num<2)
{
cout<<0<<" "<<0<<endl;
continue;
}
vector<int> arr;//arr不要声明为全局变量,不然全部测试数据都被存入了arr
int length=num;
int temp;
while(num--)//不能写成while(cin>>temp)，不然，全部测试数据都被一次性存入了arr
{
cin>>temp;
arr.push_back(temp);
}
sort(arr.begin(),arr.end());//C++排序函数：对[begin,end)内所有元素排序
//求最小值minVal
int minVal=arr[1]-arr[0];
for(i=1;i<length-1;++i)
{
int cur=arr[i+1]-arr[i];
if(cur<minVal)
minVal=cur;
}
//求最小值的个数minCount
int minCount=0;
if(minVal==0)//arr中有相等元素时
{
for(i=0;i<length-1;++i)
{
for(j=i+1;j<length;++j)
{
if(arr[i]==arr[j])
++minCount;
}
}
}
else//arr中无元素相等时
{
for(i=0;i<length-1;++i)
{
int cur=arr[i+1]-arr[i];
if(cur==minVal)
{
++minCount;
}
}
}
//求最大值maxVal
int maxVal=arr[length-1]-arr[0];
//求最大值的个数maxCount
int maxCount=0;
if(maxVal==0)//全部元素都相等,利用组合原理
{
maxCount=length*(length-1)/2;
}
else//有不同的元素,最大值的个数=最小的个数*最大的个数
{
int smallCount=0,bigCount=0;
for(i=0;i<length;++i)
{
if(arr[i]==arr[0])
++smallCount;
else if(arr[i]==arr[length-1])
++bigCount;
}
maxCount=smallCount*bigCount;
}
cout<<minCount<<" "<<maxCount<<endl;
}
return 0;
}
发表于 2018-01-02 17:10:15
回复(1)
#include <iostream>
#include <map>
#include <utility>
using namespace std;
// 用一个map来存储输入的数，当存在相同的数时不插入新的数，而是将计数值+1
int main()
{
int num;
while(cin>>num)
{
map<int,int> myMap;
bool flag = false;
for(int i = 0; i < num ; i++)
{
int k ;
cin>>k;
map<int,int>::iterator ite;
ite = myMap.find(k);
if(ite != myMap.end())
{ (*ite).second++;flag = true;}
else
{
myMap.insert(make_pair(k,1));
}
} // end of for 读取输入的数据
map<int,int>::iterator ite = myMap.begin();
int min =0;
int minv = -1;
if(flag) //如果存在相同的数
{
for( ; ite!= myMap.end(); ite++)
{
if((*ite).second > 1)
min += ((*ite).second * ((*ite).second -1 ))/2;
} //最小差元组对数等于所有相等的数构成的元组对
}
else
{
for( map<int,int>::iterator ite2 = (++myMap.begin()); (ite2)!= myMap.end(); ite2++,ite++ )
{
int k = (*(ite2)).first - (*(ite)).first;
if( minv ==-1 || k < minv )
{ min = (*ite).second * (*ite2).second ;
minv = k; }
else if(minv == k)
{
min+= (*ite).second * (*ite2).second;
}
} // end of for 求不存在相等的值时的最小差的元组对数
}// 最小对的个数
int max;
if( (*myMap.rbegin()).first != (*myMap.begin()).first)
max = (*myMap.rbegin()).second * (*myMap.begin()).second;
else
max = (*myMap.rbegin()).second *((*myMap.rbegin()).second-1)/2;//最大差的对数
cout<< min<<" "<<max<<endl;
}
}
编辑于 2016-08-16 21:14:28
回复(9)
首先吐槽一下这个编译器，是真该好好查查漏洞了。明明正确的答案，非要说是错的，那我也是没办法了。已经将时间、空间复杂度降到最低了，代码如下（JS）：
let shuru = [];
while(line = readline()){
shuru.push(line);
}
shuru.forEach((item,index)=>{
if(index % 2 != 0){
shuru[index] = item.split(' ');
}
})
function jisuan(arr){
arr.sort((a,b)=>a-b);
if(arr[0] == arr[arr.length - 1]){
let count = (arr.length * (arr.length - 1)) / 2;
console.log(count+ ' ' + count);
}else{
let minCount = 0,maxCount = 0;
let min = 0,max = 0,minIndex = 0,maxIndex = arr.length - 1;
while(arr[minIndex] == arr[0]){
min++;
minIndex++;
}
while(arr[maxIndex] == arr[arr.length - 1]){
max++;
maxIndex--;
}
maxCount = min * max;
let newArr = [];
arr.reduce((pre,now)=>{
newArr.push(Math.abs(now - pre));
return now;
})
let arr0 = [];
let preIndex;
newArr.forEach((item,index)=>{
if(item == 0){
if(newArr[index - 1] != 0){
preIndex = index;
}
if(newArr[index + 1] != 0){
arr0.push(index - preIndex + 1);
}
}
})
if(arr0.length != 0){
arr0.forEach(e=>{
minCount += (e * (e + 1)) / 2;
})
}
if(minCount > 0){
console.log(minCount + ' ' + maxCount);
}else{
newArr.sort((a,b)=>a-b);
let minIndex2 = 0;
while(newArr[minIndex2] == newArr[0]){
minCount++;
minIndex2++;
}
console.log(minCount + ' ' + maxCount);
}
}
}
shuru.forEach((item,index)=>{
if(index % 2 != 0){
item.forEach((item2,index2)=>{
shuru[index][index2] = parseInt(item2);
})
jisuan(item);
}
})
while(line = readline()){
shuru.push(line);
}
shuru.forEach((item,index)=>{
if(index % 2 != 0){
shuru[index] = item.split(' ');
}
})
function jisuan(arr){
arr.sort((a,b)=>a-b);
if(arr[0] == arr[arr.length - 1]){
let count = (arr.length * (arr.length - 1)) / 2;
console.log(count+ ' ' + count);
}else{
let minCount = 0,maxCount = 0;
let min = 0,max = 0,minIndex = 0,maxIndex = arr.length - 1;
while(arr[minIndex] == arr[0]){
min++;
minIndex++;
}
while(arr[maxIndex] == arr[arr.length - 1]){
max++;
maxIndex--;
}
maxCount = min * max;
let newArr = [];
arr.reduce((pre,now)=>{
newArr.push(Math.abs(now - pre));
return now;
})
let arr0 = [];
let preIndex;
newArr.forEach((item,index)=>{
if(item == 0){
if(newArr[index - 1] != 0){
preIndex = index;
}
if(newArr[index + 1] != 0){
arr0.push(index - preIndex + 1);
}
}
})
if(arr0.length != 0){
arr0.forEach(e=>{
minCount += (e * (e + 1)) / 2;
})
}
if(minCount > 0){
console.log(minCount + ' ' + maxCount);
}else{
newArr.sort((a,b)=>a-b);
let minIndex2 = 0;
while(newArr[minIndex2] == newArr[0]){
minCount++;
minIndex2++;
}
console.log(minCount + ' ' + maxCount);
}
}
}
shuru.forEach((item,index)=>{
if(index % 2 != 0){
item.forEach((item2,index2)=>{
shuru[index][index2] = parseInt(item2);
})
jisuan(item);
}
})
发表于 2019-04-22 17:35:13
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Jd_NumAbs {
private static Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
while (scanner.hasNext()) {
int num = scanner.nextInt();
int[] nums = new int[num];
for (int i = 0; i < num; i++) {
nums[i] = scanner.nextInt();
}
// getMinMaxAbsNums(nums, num);
fun2(nums, num);
}
}
public static void getMinMaxAbsNums(int[] nums, int len) {
int minNum = 0, maxNum = 0;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len - 1; i++) {// 时间复杂度n^2
for (int j = i + 1; j < len - 1; j++) {
int abs = Math.abs(nums[i] - nums[j]);
if (abs < min) {
minNum = 1;
min = abs;
} else if (min == abs) {
minNum++;
} else if (abs > max) {
max = abs;
maxNum = 1;
} else if (max == abs) {
maxNum++;
}
}
}
System.out.println(minNum + " " + maxNum);
}
public static void fun2(int[] nums, int len) {
Arrays.sort(nums);// 时间复杂度nlogn
int maxCount = 0;
int minNum = 1, maxNum = 1;// 数组中最小和最大元素的个数
int i = 1;
while (i < len && nums[i - 1] == nums[i]) {
minNum++;
i++;
}
i = len - 2;
while (i >= 0 && nums[i] == nums[i + 1]) {
maxNum++;
i--;
}
if (nums[0] == nums[len - 1]) {
maxCount = len * (len - 1) / 2;
} else {
maxCount = minNum * maxNum;
}
for (int j = 1; j < len; j++) {
nums[j - 1] = Math.abs(nums[j] - nums[j - 1]);
}
int minValue = Integer.MAX_VALUE;
int minCount = 0;
for (int j = 0; j < nums.length; j++) {//初次统计minValue
if (nums[j] < minValue) {
minCount = 1;
minValue=nums[j];
} else if (nums[j] == minValue) {
minCount++;
}
}
if(minValue==0){//如果最小差值为0，统计0的区间个数
minCount=0;
int tempMinCount=0;
for (int j = 0; j < len-1; j++) {
if (nums[j]==0) {
tempMinCount++;
}else {
minCount+=tempMinCount*(tempMinCount+1)/2;
tempMinCount=0;
}
}
minCount+=tempMinCount*(tempMinCount+1)/2;
}
System.out.println(minCount + " " + maxCount);
}
}
发表于 2016-07-12 17:46:52
回复(2)
import sys
for line in sys.stdin:
temp = [int(i) for i in line.split()]
if len(temp) == 1:
# 把N跳过
continue
temp.sort()
Dict = {}
for i in temp:
if i in Dict:
Dict[i] += 1
else:
Dict[i] = 1
res = 0
for k in Dict.keys():
if Dict[k] >= 2:
temp2 = [i for i in range(Dict[k])]
res += sum(temp2)
if res == 0:
# 没重复的情况，比如[1,2,3,9]这种
temp3 = []
for j in range(len(temp)-1):
temp3.append(temp[j+1] - temp[j])
temp3.sort()
# print()会换行，算例通不过，加了end就不会换行
print(temp3.count(temp3[0]), end=" ")
else:
print(res, end=" ")
num_max, num_min = Dict[temp[-1]], Dict[temp[0]]
print(num_max*num_min) 我用python3，各位一定要注意print()会直接换行，算例通不过
发表于 2021-04-01 21:23:28
回复(2)
import java.util.*;
public class Main {
public static void main(String[] args) {
///输入处理
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
//先对数组排序，方便找最大最小，也方便求每个数字的次数
Arrays.sort(num);
//如果所有的数字都相等，想想为什么要单独判断？
if (num[n - 1] == num[0]) {
int res = n * (n - 1) / 2;
System.out.println(res + " " + res);
continue; //continue返回，因为在while循环里面
//统计次数
}
//注意，此处用TreeMap，它能自动排序，因为后面
//求最大值时，需要用到
Map<Integer, Integer> map = new TreeMap<>();
for (int val : num) {
if (map.containsKey(val)) {
map.put(val, map.get(val) + 1);
} else {
map.put(val, 1);
}
}
//求最小值
int minCnt = 0;
if (map.size() == n) { //没有重复数字
int minNum = Math.abs(num[0] - num[1]);
for (int i = 1; i < n; i++) { //当需要数组中相邻的数字比较时，尤其注意数组越界的情况
int tmp = Math.abs(num[i] - num[i-1]);
if (tmp == minNum) {
minCnt ++;
} else if (tmp < minNum) {
minNum = tmp;
minCnt = 1;
}
}
} else {
for (int val : map.keySet()) {
int value = map.get(val);
if (value > 1) {
minCnt += (value * (value - 1)) / 2;
}
}
}
//求最大值
List<Integer> list = new ArrayList<>(map.keySet());
int max = map.get(list.get(0)) * map.get(list.get(list.size() - 1));
System.out.println(minCnt + " " + max);
}
}
}
发表于 2017-04-04 13:56:39
回复(0)
import sys def main(): k = 0 for line in sys.stdin: k = 1 - k if (k == 0): li = [int(i) for i in line.strip().split()] m = len(li) li.sort() small, big = li[0], li[m-1] smallnum, bignum, ansbig, anssmall, mincha, mincount = 1, 1, 0, 0, -1, 0 # answer big while (li[smallnum] == small): smallnum += 1 while (li[m-1-bignum] == big): bignum += 1 ansbig = smallnum * bignum #answer small for i in range(m-1): if (li[i+1] - li[i] < mincha or mincha < 0): mincha = li[i+1] - li[i] mincount = 1 elif (li[i+1] - li[i] == mincha): mincount += 1 if (mincha > 0): anssmall = mincount else: p = 0 for i in range(m-1): if (li[i+1] == li[i]): p += 1 else: if (p > 0): anssmall += p * (p + 1) / 2 p = 0 anssmall += p * (p + 1) / 2 print str(anssmall) + " " + str(ansbig) main()
发表于 2017-03-26 16:16:20
回复(2)
思路：
先排序
最大差：最大值-最小值
最大差的对数：最大值的数量 * 最小值的数量
取两相邻数为一对，可使差值尽可能的小。
最小差：相邻的数中，差值最小的
最小差的对数：
1. 如果最小差为0，则为 每组相等数中 任选2个的所有
组合
数。
2. 如果最小差不为0，则为 相邻数差值 = 最小差 的所有
数量。
#include <stdio.h>
#include <algorithm>
int main() {
int n, a[100000];
while(~scanf("%d", &n)) {
int t = n;
while(t--)
scanf("%d", a + t);
std::sort(a, a + n);
int j = n - 2, nMin = 1, nMax = 1;
int nMaxDiff = 0, nMinDiff = 0, minDiff = 0x7fffffff;
while(nMin < n && a[nMin - 1] == a[nMin])
nMin++;
while(j >= 0 && a[j] == a[j + 1]) {
j--;
nMax++;
}
nMaxDiff = nMin * nMax;
//find minDiff and add nMinDiff
for(int i = 1; i < n; i++) {
int d = a[i] - a[i - 1];
if(d < minDiff) {
minDiff = d;
nMinDiff = 0;
}
if(minDiff == 0)
break;
nMinDiff += (d == minDiff);
}
//minDiff = 0, find equal numbers and add nMinDiff
if(minDiff == 0) {
int m = 1;
for(int i = 1; i < n; i++) {
if(a[i] == a[i - 1]) {
m++;
} else if(m > 1) {
nMinDiff += m * (m - 1)/2;
m = 1;
}
}
nMinDiff += (m > 1) ? m * (m - 1)/2 : 0;
}
printf("%d %d\n", nMinDiff, nMaxDiff);
}
return 0;
}
编辑于 2017-01-05 14:41:32
回复(0)
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[]num=new int[n];
for(int i=0;i<n;i++)
num[i]=sc.nextInt();
Arrays.sort(num);
int min=Integer.MAX_VALUE;
int countmin=0;
for(int i=1;i<n;i++){
if(min>(num[i]-num[i-1])){
countmin=0;
min=num[i]-num[i-1];
if (min==0)
break;
}
if((num[i]-num[i-1])==min)
countmin++;
}
if(min==0){
int min_num=1;
for(int i=1;i<n;i++){
if(num[i]==num[i-1]){
min_num++;
}
else if(min_num!=1){
countmin+=min_num*(min_num-1)/2;
min_num=1;
}
}
}
int countmax=0;
int num1=0;
int num2=0;
int i=0;
while(i<n){
if(num[i]==num[0]){
num1++;
i++;}
else
break;
}
int j=n-1;
while(j>=0){
if(num[j]==num[n-1]){
num2++;
j--;}
else
break;
}
countmax=num1*num2;
System.out.println(countmin+" "+countmax);
}
}
}
测试用例只通过10%，最小对数有问题，而且是普通非相等情况出问题，不知怎么回事。
发表于 2016-09-26 17:45:37
回复(0)
C++ 哈希表(map) 实现
key存储元素值，value存储元素出现次数，map自动按照key升序排列- 注意题目所指的差值是
abs(x - y)，一定是非负数，因此(nums[i], nums[j])与(nums[j],nums[i])是一种情况，即「组合数 」
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
while (cin >> n) {
map<int, int> mp; // 自动按照键排序
while (n--) cin >> x, ++mp[x];
int maxDiffCnt = 0, minDiffCnt = 0, minDiff = INT_MAX, pre = -1;
if (mp.size() == 1) { // map中只有一个元素的情况(个数为1 或 所有元素均相同)
maxDiffCnt = mp.begin() -> second * (mp.begin() -> second - 1) / 2;
printf("%d %d\n", maxDiffCnt, maxDiffCnt);
continue; // 本次遍历结束
}
// 以下为map中含有2个及以上元素的情况
maxDiffCnt = mp.begin() -> second * prev(mp.end()) -> second;
for (auto &[num, cnt] : mp) {
if (cnt > 1) { // 含有多个值相同的元素，则最大差值为0
if (minDiff > 0) { minDiff = 0; minDiffCnt = 0; }
minDiffCnt += cnt * (cnt - 1) / 2; // 选择问题，cnt中选两个
} else { // 当前元素只有一个
if (pre == -1);
else if (num - pre == minDiff) { // 差值与之前差值相同
++minDiffCnt;
} else if (num - pre < minDiff) { // 差值比之前差值小，更新minDiff
minDiff = num - pre;
minDiffCnt = 1;
}
}
pre = num;
}
printf("%d %d\n", minDiffCnt, maxDiffCnt);
}
return 0;
}
编辑于 2022-08-20 11:18:18
回复(0)
楼上高赞大佬说得很详细，遇到相等的数就使用组合数公式，否则计数自增1。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while((line = br.readLine()) != null) {
int n = Integer.parseInt(line.trim());
String[] strArr = br.readLine().trim().split(" ");
int[] arr = new int[n];
// 统计每个数的出现次数
HashMap<Integer, Integer> counter = new HashMap<>();
int min = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(strArr[i]);
if(counter.containsKey(arr[i])){
counter.put(arr[i], counter.get(arr[i]) + 1);
min = 0;
}else
counter.put(arr[i], 1);
}
Arrays.sort(arr);
if(arr[n - 1] == arr[0]){
// 最值相等，二元组数均为数组长度n的组合数
System.out.println(n*(n - 1) / 2 + " " + n*(n - 1) / 2);
}else{
// 求最小差二元组数
int minCount = 0;
if(min == 0){
// 此时最小差值为0，二元组个数为每个重复数字出现次数的组合数之和
for(int num: counter.keySet())
if(counter.get(num) > 1) minCount += counter.get(num)*(counter.get(num) - 1) / 2;
}else{
min = Math.abs(arr[1] - arr[0]);
for(int i = 2; i < n; i++){
int temp = Math.abs(arr[i] - arr[i - 1]);
if(temp == min)
minCount++;
else if(temp < min){
min = temp;
minCount = 1;
}
}
}
// 求最大差二元组数（最大和最小数组合，即最大数的个数*最小数的个数）
int maxCount = counter.get(arr[0]) * counter.get(arr[n - 1]);
System.out.println(minCount + " " + maxCount);
}
}
}
}
发表于 2021-02-08 15:36:37
回复(0)
先使用sort排序，最大差值肯定是头尾数之差，最小值肯定出现在相邻数间
clude<iostream>
#include<vector>
(721)#include<algorithm>
using namespace std;
int main(){
int n,t;
while(cin>>n){
vector<int> nums(n);
for(int i=0;i<n;i++){
cin>>nums[i];
}
sort(nums.begin(),nums.end());
int mindis=nums[1]-nums[0];//初始值
int maxdis=nums[n-1]-nums[0];//确定值
int maxp=0,minp=0,tmp;
for(int i=0;i<n-1;i++){
mindis=min(nums[i+1]-nums[i],mindis);//找最小差值（出现在相邻数间）
}
for(int i=0;i<n;i++){
for(int j=n-1;j>i;j--){
tmp=nums[j]-nums[i];
if(tmp==maxdis) maxp++;
if(tmp==mindis) minp++;
}
}
cout<<minp<<" " <<maxp<<endl;
}
return 0;
}
编辑于 2020-03-20 15:16:20
回复(1)
- //使用c++的map，“键-值”对，可以按键进行自动排序，首先使用一个map保存输入的数据
- //“键”为输入的数据，“值”为该数据所出现的次数
- //一共分三种情况：1、所有的输入数据都相同；2、有部分输入数据相同；3、所有的数据都不同
- #include<iostream>
- #include<vector>
- #include<map>
- #include<stdlib.h>
- using namespace std;
- int difference_min_num = 0;
- void compare_fuc(map<int,int> mp1)
- {
- map<int,int>::iterator iter;
- int max_num,min_num;
- max_num = (--mp1.end())->second;
- min_num = mp1.begin()->second;
- //所有的数据都相同，表示map只有一个数，差最小和差最大均为：min_num*(min_num-1)/2
- //差最大等于：最小值的个数×最大值的个数，下同
- if(mp1.size() == 1)
- {
- cout<<min_num*(min_num-1)/2<<" "<<min_num*(min_num-1)/2<<endl;
- return;
- }
- int tmp = 1;
- vector<int> vec,vec2;
- vec2.clear();
- vec.clear();
- for(map<int,int>::iterator j = mp1.begin();j != mp1.end();j++)
- {
- //将重复的数据的“值”放入vec
- if(j->second > 1)
- vec.push_back(j->second);
- vec2.push_back(j->first);
- }
- int sum_times = 0;
- //有部分相同的数据，差最小的总次数等于每个重复数据之和 ，而
- //每个重复数据的次数为： (*i)*(*i-1)/2
- if(vec.size() != 0)
- {
- for(vector<int>::iterator i = vec.begin();i != vec.end();i++)
- sum_times += (*i)*(*i-1)/2;
- cout<<sum_times<<" "<<max_num*min_num<<endl;
- return;
- }
- int tp = abs(vec2[1] - vec2[0]);
- difference_min_num = 0;
- //所有数据都不重复
- for(int j = 0;j != vec2.size()-1;j++)
- {
- if(abs(vec2[j] - vec2[j+1]) < tp)
- {
- tp = abs(vec2[j] - vec2[j+1]);
- difference_min_num = 1;
- }
- else if(abs(vec2[j] - vec2[j+1]) == tp)
- difference_min_num++;
- }
- cout<<difference_min_num<<" "<<max_num*min_num<<endl;
- }
- int main()
- {
- int n,m;
- map<int,int> mp;
- while(cin>>n)
- {
- mp.clear();
- for(int i = 0;i != n;i++)
- {
- cin>>m;
- mp[m]++;
- }
- compare_fuc(mp);
- }
- }
发表于 2019-11-14 16:14:10
回复(0)
import sys
def qSort(lst,start,end):
"""快速排序"""
if start >= end:
return
i = start; j = end
r = lst[i] # 将lst[i]选做枢轴元素
while i < j:
while i < j and lst[j] >= r:
j -= 1
if i < j:
lst[i] = lst[j]
i += 1
while i < j and lst[i] <= r:
i += 1
if i < j:
lst[j] = lst[i]
j -= 1
lst[i] = r
qSort(lst,start,i-1)
qSort(lst,i+1,end)
def getMaxPair(lst,n):
# 数组中所有数字都相等，那么差最大的对就是它们两两组合
if lst[0] == lst[n-1]:
return n*(n-1)//2
# 找出最小的数有多少个
for i in range(1,n-1):
if lst[i] != lst[0]:
break
# 找出最大的数有多少个
for j in range(1,n-1):
if lst[n-1-j] != lst[n-1]:
break
return i*j
def getMinPair(lst,n):
# 数组中所有数字都相等，那么差最小的对就是它们两两组合
if lst[0] == lst[n-1]:
return n*(n-1)//2
mincount = 0
mindiff = lst[1] - lst[0]
count = 1
for i in range(1,n-1):
# 差为0时对数的计算方法是不一样的，所以跳出
if mindiff == 0:
break
if lst[i+1]-lst[i] == mindiff:
count += 1
elif lst[i+1]-lst[i] < mindiff:
mindiff = lst[i+1]-lst[i]
count = 1
if mindiff == 0:
for i in range(0,n-1):
# 找出差为0的段的起始点
if lst[i+1]-lst[i] == 0 and (i==0 or lst[i]-lst[i-1]>0):
start = i
# 找出差为0的段的终点
if lst[i+1]-lst[i] == 0 and (i+1==n-1 or lst[i+2]-lst[i+1]>0):
end = i+1
equalnum = end-start+1
# 可能存在多个差为0的子序列，故应分段计算，再把它们相加
mincount = mincount + equalnum*(equalnum-1)//2
return mincount
else:
return count
if __name__ == '__main__':
while True:
num = sys.stdin.readline().strip()
if not num:
break
n = int(num)
line = sys.stdin.readline().strip()
if not line:
break # 这一步不能少，否则退出时会报错
strlst = line.split(' ')
lst = list(map(int,strlst))
qSort(lst,0,n-1)
print(str(getMinPair(lst,n))+' '+str(getMaxPair(lst,n)))
发表于 2019-10-10 17:49:14
回复(0)
import sys
def MaxAndMinPair(s):
if len(s) <= 1:
return 0
s.sort(reverse=True)
if s[0] == s[-1]:
minPair = maxPair = int(len(s) * (len(s) - 1) / 2)
print(str(minPair)+' '+str(maxPair))
else:
minGap = s[0] - s[-1]
minPair = 1
for i in range(len(s)-1):
if s[i] - s[i + 1] < minGap:
minGap = s[i] - s[i + 1]
if minGap == 0:
break
minPair = 1
continue
if s[i] - s[i + 1] == minGap:
minPair += 1
if minGap == 0:
minPair = 0
elementDic = {}
for i in range(len(s)):
if s[i] not in elementDic:
elementDic[s[i]] = 1
else:
elementDic[s[i]] += 1
for key in elementDic:
num = elementDic[key]
minPair += num*(num-1)/2
# to find the max gap pair num
# 2 1 1 1
maxNum = 1
minNum = 1
for i in range(len(s)-1):
if s[i] == s[i+1]:
maxNum += 1
else:
break
for i in range(len(s)-1):
if s[len(s)-1-i] == s[len(s)-2-i]:
minNum += 1
else:
break
print(str(int(minPair)) + ' ' + str(maxNum * minNum))
if __name__ == '__main__':
k = 0
for line in sys.stdin:
k = 1 - k
if (k == 0):
data = [int(i) for i in line.strip().split()]
MaxAndMinPair(data) python3版本：
最大差对数：
在对数组排序后，最大差值只能是产生于最大的数-最小的数，所以最大差对数=最大数个数*最小数个数
最小差对数：
情况1: 如果数组中有相等的数，那么最小差为0，所以统计可以产生差值为0的所有排列组合。对于其中一组相等的数来说，产生最小差对数 = C2/n = n*(n-1)/2（排列组合数学问题），累加所有组相等数可产生的最小差对数，就是整个数组可以产生最小差的对数。
情况2:如果数组中没有相等的数，那么最小差就不为0，又因为数组是有序的，所以最小差只能产生于相邻两个数的作差，所以遍历一次数组即可求出对数
发表于 2019-09-14 11:11:27
回复(0)
贴一个排序后二分的代码，做的时候clang编译器有问题，给min_cha赋初值(long long)1e20最后一个测试数据会出错，本地g++就没问题，现在给min_cha赋值2*30就AC了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
ll A[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n = 0;
while(cin >> n){
for(int i=0;i<n;i++){
cin >> A[i];
}
sort(A,A+n);
ll min_cha = 1<<30;
for(int i=1;i<n;i++){
min_cha = min(min_cha,A[i]-A[i-1]);
}
ll ans1 = 0;
for(int i=0;i<n-1;i++){
int t = upper_bound(A,A+n,A[i]+min_cha)-A;
ans1 += (t-i-1);
}
ll max_cha = A[n-1] - A[0];
ll ans2 = 0;
for(int i=0;i<n;i++){
int t = lower_bound(A+i,A+n,A[i]+max_cha)-A;
ans2 += (n-t);
}
cout << ans1 << " " << ans2 << endl;
}
return 0;
}
编辑于 2018-10-05 15:06:24
回复(0)
问题信息
通过挑战的用户
-
2023-02-25 15:51:52
-
2022-11-17 00:02:22
-
2022-11-16 22:47:21 -
2022-11-10 23:13:02
-
2022-10-16 19:29:25
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
