本专栏为c语言练习专栏，适合刚刚学完c语言的初学者。本专栏每天会不定时更新，通过每天练习，进一步对c语言的重难点知识进行更深入的学习。
今日练习题关键字：两个数组的交集 双指针
💓博主csdn个人主页：小小unicorn
⏩专栏分类：C语言天天练
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
题目一：
题目描述：
给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。
解题思路：
遍历数组分别找到数组的最大值 m1 和次大值 m2 。如果 m1≥m2×2 成立，则最大值至少是数组其余数字的两倍，此时返回最大值的下标，否则返回 −1-1−1。
为了返回最大值的下标，我们需要在计算最大值的同时记录最大值的下标。
代码实现：
int dominantIndex(int* nums, int numsSize)
{
int m1 = -1, m2 = -1;
int index = -1;
for (int i = 0; i < numsSize; i++)
{
if (nums[i] > m1)
{
m2 = m1;
m1 = nums[i];
index = i;
} else if (nums[i] > m2)
{
m2 = nums[i];
}
}
return m1 >= m2 * 2 ? index : -1;
}
结果情况：
符合题目要求，题目得到解决。
题目二：
题目描述：
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
解题思路------两个集合：
思路一：
计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。
假设数组 nums1 和 nums2 的长度分别是 m 和 n，则遍历数组 nums1 需要 O(m) 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间，因此总时间复杂度是 O(mn)。
如果使用哈希集合存储元素，则可以在 O(1)的时间内判断一个元素是否在集合中，从而降低时间复杂度。
首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)。
代码实现：
struct unordered_set
{
int key;
UT_hash_handle hh;
};
struct unordered_set* find(struct unordered_set** hashtable, int ikey)
{
struct unordered_set* tmp;
HASH_FIND_INT(*hashtable, &ikey, tmp);
return tmp;
}
void insert(struct unordered_set** hashtable, int ikey)
{
struct unordered_set* tmp = find(hashtable, ikey);
if (tmp != NULL) return;
tmp = malloc(sizeof(struct unordered_set));
tmp->key = ikey;
HASH_ADD_INT(*hashtable, key, tmp);
}
int* getIntersection(struct unordered_set** set1, struct unordered_set** set2, int* returnSize)
{
if (HASH_COUNT(*set1) > HASH_COUNT(*set2))
{
return getIntersection(set2, set1, returnSize);
}
int* intersection = malloc(sizeof(int) * (HASH_COUNT(*set1) + HASH_COUNT(*set2)));
struct unordered_set *s, *tmp;
HASH_ITER(hh, *set1, s, tmp)
{
if (find(set2, s->key))
{
intersection[(*returnSize)++] = s->key;
}
}
return intersection;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
*returnSize = 0;
struct unordered_set *set1 = NULL, *set2 = NULL;
for (int i = 0; i < nums1Size; i++)
{
insert(&set1, nums1[i]);
}
for (int i = 0; i < nums2Size; i++)
{
insert(&set2, nums2[i]);
}
return getIntersection(&set1, &set2, returnSize);
}
思路二----排序加双指针：
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre\textit{pre}pre 表示上一次加入答案数组的元素。
初始时，两个指针分别指向两个数组的头部。
每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre\textit{pre}pre ，将该数字添加到答案并更新 pre\textit{pre}pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
代码实现：
int cmp(void* a, void* b)
{
return *(int*)a - *(int*)b;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
qsort(nums1, nums1Size, sizeof(int), cmp);
qsort(nums2, nums2Size, sizeof(int), cmp);
*returnSize = 0;
int index1 = 0, index2 = 0;
int* intersection = malloc(sizeof(int) * (nums1Size + nums2Size));
while (index1 < nums1Size && index2 < nums2Size)
{
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2)
{
// 保证加入元素的唯一性
if (!(*returnSize) || num1 != intersection[(*returnSize) - 1])
{
intersection[(*returnSize)++] = num1;
}
index1++;
index2++;
}
else if (num1 < num2)
{
index1++;
}
else
{
index2++;
}
}
return intersection;
}
结果情况：
符合题目要求，问题得到解决。文章来源：https://www.toymoban.com/news/detail-683997.html
总结：
文章到这里就要告一段落了，有更好的想法或问题，欢迎评论区留言。
希望今天的练习能对您有所收获，咱们下期见！文章来源地址https://www.toymoban.com/news/detail-683997.html
到了这里，关于C语言每日一练------------Day(7)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
