问题描述
王多鱼，我是你二爷，你现在是我唯一的继承人，没想到你竟然能混过我的第一个考验，听好了，我给你出了一个难题，如果你能在30天内解决遗嘱上的题目，你就能继承我的三百亿遗产。怎么样，孙子？敢接受挑战吗？我很怀疑你的胆量，所以我在遗嘱上加了一条懦夫条款，你可以当做这一切都没发生，拿1000万走人，或者，你可以赌把大的。三百亿！但是如果挑战失败，你一块钱都得不到。王多鱼打开遗嘱，遗嘱上写道： 给定n个整数，问这些数中有多少对整数，它们的值正好相差1。 王多鱼当然是选择三百亿的考验，眼看已经是第29天了，王多鱼没有任何思路，所以他求助于你，聪明的你能帮王多鱼解决难题，让他得到三百亿的遗产吗？
输入描述
输入的第一行包含一个正整数n（n不超过10000），表示给定整数的个数。第二行包含所给定的n个整数（给定的整数均为不超过30000的正整数）
输出描述
输出一个整数，表示值正好相差1的数对的个数
样例输入
20
15 4 20 16 2 3 18 14 8 9 9 5 1 17 5 2 12 20 3 9
样例输出
9
#include<stdio.h>
int main()
{
int a[20000];
int k[20000];
int b,c,d,e,f,g=0,h,j=0,l=0;
scanf("%d",&b);
for(c=0;c<b;c++)
{
scanf("%d",&a[c]);
}
for(c=0;c<b-1;c++)
{
for(e=c+1;e<b;e++)
{
f=a[c]-a[e];
if(f==1||f==-1)
{
h=a[e]+a[c];
k[g]=h;
g++;
}
}
}
for(c=0;c<g-1;c++)
{
for(e=c+1;e<g;e++)
{
if(k[c]-k[e]==0)k[e]=0;
}
}
for(c=0;c<g;c++)
{
if(k[c]!=0)j++;
}
printf("%d",j);
return 0;
}
https://blog.csdn.net/qq_63062965/article/details/124527276
需不需要考虑输入的数据可能有重复？比如输入四个数6 9 9 8，最终结果应该输出1还是2？
以下是C语言的代码实现，其中使用了一个数组记录每个数字出现的次数，然后遍历数组，对于每个数字，判断其与相邻数字的差是否为1，如果是，则将它们出现次数的乘积累加到结果中。
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
scanf("%d", &n);
int* nums = (int*)malloc(n * sizeof(int));
int max_num = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
if (nums[i] > max_num) {
max_num = nums[i];
}
}
int* counts = (int*)calloc(max_num + 1, sizeof(int));
for (int i = 0; i < n; i++) {
counts[nums[i]]++;
}
int result = 0;
for (int i = 0; i < max_num; i++) {
if (counts[i] > 0 && counts[i + 1] > 0) {
result += counts[i] * counts[i + 1];
}
}
printf("%d\n", result);
free(nums);
free(counts);
return 0;
}
解释如下：
首先读入整数的个数n和n个整数，使用动态内存分配申请nums数组存储这些整数。同时记录下这些整数中的最大值max_num，以便后面申请counts数组使用。
接下来使用calloc函数申请counts数组，将其中所有元素初始化为0，并遍历nums数组，对于每个数字，在counts数组中对应位置的计数加1。
最后遍历counts数组，对于每个数字，判断它与相邻数字的差是否为1，如果是，则将它们出现次数的乘积累加到结果中。最终输出结果即可。
注意：本题中的数字范围不超过30000，因此可以使用数组记录出现次数，如果数字范围更大，可以考虑使用哈希表等数据结构来记录。
另外，如果使用哈希表来记录出现次数，可以将时间复杂度降低到O(n)，具体实现如下：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
int value;
struct Node* next;
} Node;
typedef struct HashTable {
int size;
Node** table;
} HashTable;
int hash(int key, int size) {
return key % size;
}
Node* create_node(int key, int value) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->value = value;
node->next = NULL;
return node;
}
HashTable* create_hash_table(int size) {
HashTable* hash_table = (HashTable*)malloc(sizeof(HashTable));
hash_table->size = size;
hash_table->table = (Node**)calloc(size, sizeof(Node*));
return hash_table;
}
void insert(HashTable* hash_table, int key) {
int index = hash(key, hash_table->size);
Node* node = hash_table->table[index];
if (node == NULL) {
hash_table->table[index] = create_node(key, 1);
} else {
while (node->next != NULL) {
if (node->key == key) {
node->value++;
return;
}
node = node->next;
}
if (node->key == key) {
node->value++;
} else {
node->next = create_node(key, 1);
}
}
}
int find(HashTable* hash_table, int key) {
int index = hash(key, hash_table->size);
Node* node = hash_table->table[index];
while (node != NULL) {
if (node->key == key) {
return node->value;
}
node = node->next;
}
return 0;
}
int main() {
int n;
scanf("%d", &n);
int max_num = 0;
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
if (num > max_num) {
max_num = num;
}
}
HashTable* hash_table = create_hash_table(n);
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
insert(hash_table, num);
}
int result = 0;
for (int i = 0; i < max_num; i++) {
if (find(hash_table, i) > 0 && find(hash_table, i + 1) > 0) {
result += find(hash_table, i) * find(hash_table, i + 1);
}
}
printf("%d\n", result);
return 0;
}
这里使用了链表来处理哈希表中的冲突。具体实现过程中，使用create_node函数创建一个新的节点，使用create_hash_table函数创建一个新的哈希表，使用insert函数向哈希表中插入一个键值对，使用find函数查找哈希表中某个键对应的值。
在主函数中，先读入整数的个数n和n个整数，记录下这些整数中的最大值max_num，以便后面申请哈希表使用。接下来创建哈希表，并遍历输入的整数，将它们插入到哈希表中。最后遍历哈希表，对于每个数字，判断它与相邻数字的差是否为1，如果是，则将它们出现次数的乘积累加到结果中。最终输出结果即可。
总的来说，哈希表是一种非常高效的数据结构，可以用来解决各种查找问题。
C++实现
算法思路：使用哈希表（字典）来记录每个数出现的次数，然后遍历哈希表，判断每个数是否和前一个数相差为1，如果相差为1，则将这两个数出现次数的乘积加入结果中。
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
freq[num]++;
}
int ans = 0;
int prev = 0;
for (auto it = freq.begin(); it != freq.end(); it++) {
int num = it->first;
if (prev != 0 && num - prev == 1) {
ans += freq[prev] * freq[num];
}
prev = num;
}
cout << ans << endl;
return 0;
}
输入格式：
输入的第一行包含两个整数n,m，表示节目的数量。第二行包含n个整数，依次为每个节目的好看值。
输出格式：
输出一行包含m个整数，为选出的节目的好看值。
样例输入：
5 3
3 1 2 5 4
样例输出：
3 5 4
评测用例规模与约定：
对于30%的评测用例，1<=n<=20;
对于60%的评测用例，1<=n<=100;
对于所有评测用例，1<=n<=100000,0<=节目的好看值<=100000。
这道题可以使用双指针对数组排序并依次扫描，寻找符合条件的数对。具体做法如下：
对给定的n个整数进行排序。
定义两个指针，分别指向排序后的数组中的第一个和第二个元素。
对于指针指向的两个元素，如果它们的值正好相差1，说明找到一对符合条件的数对。将这个数对的数量加1，并将两个指针都向右移动一位。
如果指针指向的两个元素的差值大于1，说明当前指向的两个元素之间不存在符合条件的数对，将左侧指针向右移动一位。
重复步骤3和4，直到右侧指针扫描完整个排序后的数组为止。最终统计符合条件的数对数量即可。
下面是相应的 Python 代码实现：
n = int(input())
nums = list(map(int, input().split()))
nums.sort() # 对数组进行排序
left, right = 0, 1
count = 0
while right < n:
if nums[right] - nums[left] == 1: # 存在符合条件的数对
count += 1
left += 1
right += 1
elif nums[right] - nums[left] > 1: # 数值之差大于1
left += 1
else: # 数值之差小于1，继续扫描下一个数字
right += 1
print(count)
时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$。
以下内容引用自GPT:
以下是求解此问题的 C 语言代码示例，可以使用双层循环枚举所有数对，并判断它们是否满足给定条件。
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
scanf("%d", &n);
int a[n];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int count = 0; // 值差为1的数对的个数
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (abs(a[i] - a[j]) == 1) { // 判断值差是否为1
count++;
}
}
}
printf("%d\n", count);
return 0;
}
通过此代码，您可以输入整数序列，并得到满足值差为1的数对的个数。当然，在处理大规模数据时还需要考虑算法复杂度优化的问题，可以使用哈希表等数据结构来提高效率。