c语言做网站后台服务,wordpress .htaccess 伪静态,大良营销网站建设流程,wordpress 显示相册红豆不堪看#xff0c;满眼相思泪 本文主要是帮助大家熟练掌握利用数组进行有关判断的题目#xff0c;看完本文后在之后的刷题中都可以利用这种思想#xff0c;当然举例中的题目利用该种方法可能不是最优解#xff0c;但绝对是你看到题目不用思考太多就可以做出来的方法满眼相思泪 本文主要是帮助大家熟练掌握利用数组进行有关判断的题目看完本文后在之后的刷题中都可以利用这种思想当然举例中的题目利用该种方法可能不是最优解但绝对是你看到题目不用思考太多就可以做出来的方法当然我也会介绍所列题目的其他方法以供大家思考话不多说进入正题。 基数排序 思想已经给定一个数组数组中就是我们需要排序的数列再开辟一个数组该数组的个数n为要排序的数中最大的数1且全部初始化为0根据需要排序数组中的数找到新开辟的数组中该数的下标的位置将该位置的数。 例如 逻辑很简单直接谈如何优化一眼看出某种情况下这种思路排序开的空间太大了就比如要排序的数全部在1000~2000之间的数我们从0开始开空间那么前1000的空间就是白开了造成很大的空间浪费。 我们可以先进行遍历找到要排序数组中最大值和最小值两者作差再加1就是我们需要开的空间。 代码如下
//基数排序
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 0; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;int* count (int*)malloc(sizeof(int) * range);if (count NULL){perror(malloc fail);return;}memset(count, 0, sizeof(int) * range);//统计数据出现的次数for (int i 0; i n; i){count[a[i] - min];//开的空间是减去min的所以排序数组中的数在存储时也要减去min。}int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;//该位置的数出现几次就统计出几次}}
}基数排序总结
计数排序在数据范围集中时效率很高但是适用范围及场景有限。如果是小数呢你就无法用下标进行存储了。时间复杂度O(N(范围))空间复杂度O(N) OK介绍5个用到该思想的题目帮大家掌握住这种做题方法 1错误的集合 这道题的解法很多 思路一最容易想到的就是先排序然后就可以很轻易的找到消失的数字而且我们已经知道了包含1到n可以直接求和减去出现差错的数组中的所有元素例如将5复制成了7减完之后结果为-2那么重复的数就是5加上2为7。 思路二直接利用基数排序的思想。重新开一个数组初始化全部为0不用排序直接用所给集合里面的所有数对应的下标位置加加当然如果没出现某个数那么新开数组这个位置的数就是0重复的就是1。 代码如下
int* findErrorNums(int* nums, int numsSize, int* returnSize)
{int *array1,*array2,i;array1(int*)calloc(numsSize,sizeof(int));array2(int*)malloc(sizeof(int)*2);for(i0;inumsSize;i){array1[nums[i]-1]1;}for(i0;inumsSize;i){if(array1[i]2)array2[0]i1;else if(array1[i]0)array2[1]i1;}*returnSize2;return array2;
}逻辑清晰时间复杂度为O(N),空间复杂度为O(N)。当然也可以加一个判断当已经找到两个数字后直接跳出循环减少循环次数。 2,字符个数统计 同样还是找一段区间中是否存在某个数或者某个数出现的次数字符也是整形可以利用字符表示的整形还是同样依照上边的那种思路进行解题只需要强制转化其他思路全部相同。 代码如下
#include stdio.h
int main() {int i 0;int count 0;char arr1[500];int arr[127] { 0 };scanf(%s, arr1);while (arr1[i] ! \0){arr[(int)arr1[i]] 1;i;}for (int j 0; j 127; j){if (arr[j] 1){count;}}printf(%d, count);return 0;
}同样只要使用这种思路时间复杂度一般都是O(N)由于题目都说了范围在0~127之间用这种思路多爽啊。 3多数元素 给定数组找到数组中出现次数大于numsSize/2的数我们还可以使用这种方法但是这道题使用这种方法跑不过虽然已经知道了我们要开多少的空间时间复杂度为O(1)但是数组中数的最大值和最小值相差2*10^9这个数字太大了意味着我们要开的空间也是非常大的这道题要想用时间复杂度为O(N),用这种方法是跑不过的。但是可以骗骗分正如上边所说介绍的是一种思路而已当然还会给出另外的解法。 利用数组下标做法代码如下啊
int majorityElement(int* nums, int numsSize) {int min nums[0], max nums[0];for (int i 0; i numsSize; i){if (nums[i] min){min nums[i];}if (nums[i] max){max nums[i];}}int rangemax-min1;int*arr(int*)malloc(sizeof(int)*(range));for (int k 0; k range; k){arr[k] 0;}for (int i 0; i numsSize; i){arr[nums[i] - min];}for(int j0;jrange;j){if(arr[j]numsSize/2){return jmin;}}return -1;
}仔细观察可以发现和前边基数排序的方法手段如此相像只不过在存储完成后要判断或得到的东西不同而已。 用这个代码跑的话是通过不了的因为某些用例专门针对。 可以发现过了大部分用例 剩下的估计都含有这两个数字不知道优化能不能成功也不想费那么多事如果用例中数组内的数字差别没有这么大那么这种解法的时间复杂度为O(N)空间复杂度为O(1)。 OK不能就这么摆着一个不能通过的方法在这里 谈一谈投票法很巧妙 利用该数组中多数元素的次数绝对大于numsSIze/2这一特性所以用不同的元素消去相同的对象那么身下到最后的绝对是相同元素即我们要找的多数元素。 代码如下
int majorityElement(int*nums,int numsSize)
{int candidatenums[0];int flag1;for(int i1;inumsSize;i){if(nums[i]candidate){flag;}else{flag--;if(flag0){candidatenums[i];flag1;}}}return candidate;
}4,找到所有数组中消失的数据 同样这道题也是与数组中某个数字是否存在或者某个数字出现了几次的问题利用同样的思路不需要排序即可找出且时间复杂度为O(N)但是我们开了额外的空间至于进阶的写法先放一放。 代码如下
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){int k0;int*arr(int*)malloc(sizeof(int)*(numsSize));int*ret(int*)malloc(sizeof(int)*(numsSize));//memset(arr,0,(sizeof(int)*(numsSize1)));for(int l0;lnumsSize;l){arr[l]0;}for(int i0;inumsSize;i){arr[nums[i]-1];}for(int j0;jnumsSize;j){if(arr[j]0){ret[k]j1;//*returnSize;}}*returnSizek;return ret;
}总结判断数组中某数尤其是无序出现的个数判断有没有出现就是出现个数是不是0嘛就可以使用这种方法和基数排序原理一样空间换时间开空间时一定要的。 结束啦结束啦希望你有所收获这就是我创作的最大动力。
