【C语言篇】C语言常考及易错题整理DAY2

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

示例 1：

输入：nums = [3,6,1,0]
输出：1
解释：6 是最大的整数，对于数组中的其他整数，6 至少是数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。

示例 2：

输入：nums = [1,2,3,4]
输出：-1
解释：4 没有超过 3 的两倍大，所以返回 -1 。

暴力破解：双重循环遍历数组，对每个元素判断是否是其他元素的两倍。或者先遍历一遍找出最大值，然后遍历一遍判断是否是其他数字二倍。

更优思想：一次遍历找出最大的数字和次大的数字，判断最大的数字是否是次大数字2倍即可

int dominantIndex(int* nums, int numsSize){if (numsSize == 1) return 0;//特殊情况只有一个元素则特殊处理int max, sec, idx;//先对最大和次大进行选择赋值，注意max和sec不能随意赋初值，因为有可能你赋予的初值就是最大值//因此要使用数组中的数据进行初值赋予。if (nums[0] > nums[1]) {max = nums[0];idx = 0;sec = nums[1];}else {max = nums[1];idx = 1;sec = nums[0];}for (int i = 2; i < numsSize; i++) {if (nums[i] > max) { //当前元素大于max，则意味着要替换sec = max; //先将原先最大的保存到sec中，则他就是次大的max = nums[i]; //再将最大的放到max中idx = i; //保存max值的下标}else if (nums[i] > sec){//避免刚好nums[0]就是最大的情况，因为不切换最大而导致次大无法判断情况sec = nums[i];}}if (max >= sec * 2) {return idx;}return -1;
}

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

哈希表，将两个数组的元素当做哈希数组的下标，若出现则将其下标存储数据置为1，当且仅当两个哈希数组对应下标存储的数据都是1时说明这个元素在两个数组都出现过，返回创建的数组即可

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int hash1[1001] = {0};int hash2[1001] = {0};for(int i = 0; i < nums1Size; i++){hash1[nums1[i]] = 1;}for(int i = 0; i < nums2Size; i++){hash2[nums2[i]] = 1;}int *ret = (int*)malloc(sizeof(int)*1001);int k = 0;for(int i = 0; i < 1001; i++){if(hash1[i] == 1 && hash2[i] == 1){ret[k++] = i;}}*returnSize = k;return ret;
}

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

从数组的0下标处开始向后逐下标统计，计算当前下标左边之和，和右边之和，进行判断，相等则为中心下标，如 果数组循环结束都没有找到中心下标，则返回-1，表示没有中心下标。

int pivotIndex(int* nums, int numsSize){int i, j;for (i = 0; i < numsSize; i++) {//从假设中心点为0开始进行统计判断int l_sum = 0, r_sum = 0;//初始化左边之和和右边之和为0for (j = 0; j < numsSize; j++) {if (j < i) l_sum += nums[j]; //小于i坐标的都是左边的数字else if (j > i) r_sum += nums[j];//大于i坐标的都是右边的数字}if (l_sum == r_sum) {//如果两遍相等则i就是中心坐标return i;}}return -1;
}

优化解法:

先计算总共的和，再遍历

int pivotIndex(int* nums, int numsSize) {int total = 0;for (int i = 0; i < numsSize; ++i) {total += nums[i];}int sum = 0;for (int i = 0; i < numsSize; ++i) {if (2 * sum + nums[i] == total) {return i;}sum += nums[i];}return -1;
}

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

**一个数组中有一个数字出现次数大于 n/2 ，从第 0 个字符开始，假设它就是最多的那个数字，遇到相同的数字则 计数 +1 ， 遇到不同的则计数 -1 ，其实就是互相消耗，等到计数为 0 的时候，表示本次互拼完毕，从下一个字符重 新开始互拼，但是归根结底出现次数大于 n/2 的这个数字数量更多，因此也是最后保留的字符。 **

示例： “23335” 首先从字符 2 开始计数 1 ，遇到 3 ，不同则 -1 ，互拼消耗重新从剩下的 “335” 开始的过程，这时候保存的字符为 3 ，遇到 3 则计数 +1 ， 遇到5则计数 -1 ，在计数不为 0 时，走到末尾保存的字符就是个数超过 n/2 的字符

基于一个很简单的数学原理，当一个数出现次数超过一堆数的一半时，任意相消掉两个不同的数据，这个数在新的这一堆数据中还是保留原来的特性

int majorityElement(int* nums, int numsSize) {int count = 1;int candidate = nums[0];for (int i = 1; i < numsSize; i++) {if (nums[i] == candidate)count++; else {if (count == 0)//前面的数据已经两两相消完了，只用在新的数据中开始继续找即可{candidate = nums[i];count=1;}elsecount--;}}return candidate;
}

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30

注意：不要使用除法

将乘积分为两次进行，第一次先将每个位置左边的数据乘积计算出来放到返回数组中，后边第二次循环
将对应位置右边的数据乘积计算出来与返回数组对应位置的左半边乘积相乘得到结果。

示例： 一个数组 int nums[] = {2, 3, 4} 。
int left = 1, right = 1;
计算左侧乘积：
第0个元素的左边乘积， arr[0] = left 然后计算第1位左侧乘积 left*=nums[0] -> left = 1*2
第1个元素的左边乘积， arr[1] = left 然后计算第2位左侧乘积 left*=nums[1] -> left = 1*2*3
第2个元素的左边乘积， arr[2] = left 然后计算第3位左侧乘积 已经没必要了，因为第2元素是末尾元素了
一次循环完毕后，返回数组中每个元素存储的都是自己左侧元素的乘积。 arr[]中的值： [1, 2, 6]
计算右侧乘积：
第2个元素的右边乘积， arr[2] *= right 然后计算第1位右侧乘积 right*=nums[2] -> right =1*4
第1个元素的右边乘积， arr[1] *= right 然后计算第0位右侧乘积 right*=nums[1] -> right =1*4*3
第0个元素的右边乘积， arr[0] *= right 然后计算第-1位右侧乘积 -1位已经不需要计算了
循环完毕后，返回数组中的每个元素都是其他元素的乘积了 arr[2]*=1； arr[1]*=4; arr[0]*=12

int* productExceptSelf(int* nums, int numsSize, int* returnSize){int *ret = (int *)malloc(numsSize * sizeof(int));*returnSize = numsSize;int left = 1, right = 1;//第一次循环，将当前位置左边的数字乘积填入返回数组中for (int i = 0; i < numsSize; i++) {ret[i] = left;// 1 nums[0] nums[0]*nums[1] num[0]*nums[1]*nums[2] ....left *= nums[i];}//第二次循环，对于返回数组的元素从后往前进行，每次乘以右边元素的乘积for (int i = numsSize - 1; i >= 0; i--) {ret[i] *= right; //最后一个不需要乘以最后元素，乘以1就行right *= nums[i]; //right变化：1 nums[end] nums[end]*nums[end-1] .....}return ret;
}