求单独出现的数,冒泡排序优化,strncpy的优化
求未配对的数(1):
站在用户的角度思考问题,与客户深入沟通,找到界首网站设计与界首网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:网站建设、成都网站设计、企业官网、英文网站、手机端网站、网站推广、域名申请、网站空间、企业邮箱。业务覆盖界首地区。
在一组数据中有 只有一个数出现了一次,其余的数都是成对的出现,请找出这个数:这个题很容易解决,只要把这组数据全部异或(相同为零,不同为1),所以出现两次的数异或后就为零,最后剩下的就是出现一次的数。
#include#include int find_once_num(int arr[], int len ) { int num = 0; for (int i = 0; i < len; i++) { num ^= arr[i]; } return num; } int main() { int arr[9] = { 8, 4, 2, 7, 9, 8, 4, 2, 7 }; int ret=find_once_num(arr,9); printf( "%d\n",ret); system( "pause"); return 0; }
(2)
现在将题目变一下,一组数据中只有两个数出现了一次,其余数字都是成对出现的,请找出这两个数,这时就不能直接异或了,必须将这一组数据分成两块,每块只包含一个单独出现的数,这样剩下的问题就和第一题一样了,可关键是怎么分呢???
分析:我们可以先对这组数据进行排序,这样成对出现的数就相邻在一起了,我们再一对一对的比较,直到找到第一对不相等的数,然后从中分开,这样就分成两块了。
void bubble_sort(int arr[], int n ) { int flag = 0; int i = 0; int j = 0; for (i = 0; i < n - 1; i++) { flag = 1; for (j = 0; j < n - i - 1; j++) { if (arr [j]>arr[j + 1]) { arr[j] = arr [j] + arr[j + 1]; arr[j + 1] = arr [j] - arr[j + 1]; arr[j] = arr [j] - arr[j + 1]; flag = 0; } } if (flag == 1) break; } } int find_one_num(const int *p1,int len) { assert(p1 ); int num = 0; for (int i = 0; i <=len; i++) { num ^= p1[i]; } return num; } int main() { int arr[10] = {0 ,1, 13, 18, 18,13,1,46,0,3}; int i = 0; int *p = arr; bubble_sort(arr, 10); for (i = 0; i < 10 - 1;) { if (p[i] == p[i + 1]) { i += 2; } else break; } printf( "%d %d \n", find(p, i),find((p+i+1),9-i-1)); system( "pause"); return 0; }
冒泡排序的优化:
上面对数组进行排序时,用到了冒泡排序法,通常我们使用冒泡排序法时会将每个数都与后面的数进行比较,这样虽然可以实现冒泡排序,但是却不是最优的方法,因为冒泡排序还可以进行优化。
优化:以升序为例
void bubble_sort(int arr[], int n ) { int flag = 0; int i = 0; int j = 0; for (i = 0; i < n - 1; i++) { flag = 1; //设置一个标记flag for (j = 0; j < n - i - 1; j++) { //如果第1,2有序,第2,3也有序,后面的都有序,则不进入if,flag就不会变成0 if (arr [j]>arr[j + 1]) { arr[j] = arr [j] + arr[j + 1]; arr[j + 1] = arr [j] - arr[j + 1]; arr[j] = arr [j] - arr[j + 1]; flag = 0; //只要前一个数大于后一个数,进入if,flag会变成1 } } if (flag == 1) break; //如果flag为1,则就说明这组数据已经有序 } }
strncpy的优化:
当n很大很大时,如果一个字节一个字节的copy效率会非常低下,所以我们要想一个办法,当n特别大时,使得一次性可以copy多个字节。其实这个办法就是强制类型转换,将char *转换为int *(在c中试了一下转换为double*,显示无法转换),这样一次就可以copy 4个字节,而当n小于4时再转换为char*进行copy.
#include#include #include char* my_strncpy(char *dst, const char *src, int len) { assert(dst); assert(src); int* p1= (int *)dst; const int* p2 = (int *)src; while (len) { if (len < 4) { (char *)*p1=(char *)*p2; ((char* )p1)++; ((char *)p2)++; len--; } else { *p1++ = *p2++; len -= 4; } } (char *)*p1 = '\0'; return dst; } int main() { char arr1[100]; char arr2[50]; int n = 0; scanf("%s%s%d", arr1, arr2,&n); char *ret = my_strncpy(arr1, arr2, n); printf("%s\n",ret); system("pause"); return 0; }
网站栏目:求单独出现的数,冒泡排序优化,strncpy的优化
文章转载:http://scyanting.com/article/jgshoh.html