怎么做网站图标,克隆网站带后台,团支部智慧团建网站,上海网页制作费用本专栏为c语言练习专栏#xff0c;适合刚刚学完c语言的初学者。本专栏每天会不定时更新#xff0c;通过每天练习#xff0c;进一步对c语言的重难点知识进行更深入的学习。 今日练习题关键字#xff1a;两个数组的交集 双指针 #x1f493;博主csdn个人主页#xf… 本专栏为c语言练习专栏适合刚刚学完c语言的初学者。本专栏每天会不定时更新通过每天练习进一步对c语言的重难点知识进行更深入的学习。 今日练习题关键字两个数组的交集 双指针 博主csdn个人主页小小unicorn ⏩专栏分类C语言天天练 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 Day1 题目一题目描述解题思路代码实现结果情况 题目二题目描述解题思路------两个集合思路一代码实现思路二----排序加双指针代码实现 结果情况 总结 题目一
题目描述 给你一个整数数组 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(mn)。
代码实现
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;
}
结果情况 符合题目要求问题得到解决。
总结 文章到这里就要告一段落了有更好的想法或问题欢迎评论区留言。 希望今天的练习能对您有所收获咱们下期见
