求两个自然数组中的交集

题目:有2个自然数组 里面的保存着100以内的自然数,编程求出两个数组的交集。数组中可能有重复的数字,输出的交集中不包含重复的数字。   我的实现代码如下:#include <stdio.h> #include <string.h> /*输出交集数组,同时返回交集元素个数*/ int NaturalUnion(int a, size_t len_a, int b, size_t len_b, int c) {         int tmp;         int i,index=0;         if(a && b && (len_a != 0) && (len_b != 0))         {                 memset(tmp,-1,sizeof(tmp)/sizeof(int));                 for(i=0;i<len_a;i++)                 {                         tmp = a;                 }                 for(i=0;i<len_b;i++)                 {                         if(b == tmp)                         {                                 c = tmp;                         }                 }         }         return index; } int main(int argc,char *argv) {         int a = {1,2,3,3,4,6};         int b = {3,4,5,7,8,9,10};         int c;         int count = 0,i;         count = NaturalUnion(a,sizeof(a)/sizeof(int),b,sizeof(b)/sizeof(int),c);         for(i=0;i<count;i++)         {                 printf("%d\n",c);         }         return 0; }  
阅读全文

回溯法

回溯法是一种比枚取发更好的算法,回溯法有一定的框架,这里先给出回溯的法的一般框架: //m表示数组有m个元素,n表示数组的最大元素值为n 输入正整数n, m(n>=m) i = 0; a = <元素初始值> while (1) { // i每次取得的值,和前面已得到的值进行比较,看是否能满足 for (g = 1, k = i - 1; k >= 0; k--) { if (<约束条件1>) g = 0; //检测约束条件,不满足返回 } if (g && <约束条件2>) { print(a) //输出一个解 } if (g && i < m) { i++; a = <元素初始值>; contiue; } while (a == <回溯点> && i > 0) { i--; //向前回溯 } // 达到退出循环的条件 if (i == 0 && a == <回溯点>) { break; } else { a++; } } 下面用回溯法来解决一个典型的回溯问题,八皇后问题,问题描述就省率了,直接上算法 #include <stdio.h> #include <stdlib.h> int main(int argc, const char *argv) { int...
阅读全文
算法

串的模式匹配算法

一.朴素模式匹配算法 int strsub(const char* par, const char* sub, int pos)    算法的基本思想:从主串par的第pos字符开始和子串sub的第一个字符比较,若相等,则继续捉个比较后续字符,否则则从主串的下一个字符起在重新和子串sub起始字符开始比较。以此类推,直至主串par中每个字符和子串sub的连续序列相等,则匹配相等,返回子串sub在主串par中的序号。否则匹配不成功,返回-1.下面是一个算法的实现 #include <stdio.h> #include <string.h> /* --------------------------------------------------------------------------*/ /** * @brief 从主串中的指定位置查找指定的子串是否存在 * * @param par 主串 * @param sub 子串 * @param pos 从主串中的指定位置 * * @returns 如果存在返回在主串中的位置,不存在返回-1 */ /* ----------------------------------------------------------------------------*/ int strsub(const char* par, const char* sub, int pos) { /* i为主串当前位置的指针,j为子串当前位置的指针 */ int i = pos, j = 0; int par_len = strlen(par); int sub_len = strlen(sub); int ret = -1; while (i < par_len && j < sub_len) { if (par == sub) { /* 当主串和子串当前字符相等时,指针前移 */ i++; j++; } else { /* 当有元素不相等时,则主串回退,子串从头开始 */ i...
阅读全文

找出数组中的最值,去除重复元素

在下面的数组中找出数组的最值(最大值和最小值) int array = {2, 3, 1, 4, 9, 8, 5, 10, 7, 6}; 当时我的想法是数组中每个元素肯定是要遍历的,因为要有最大值和最小值寻找,所以要有2n次的比较,当时就在想是不是要在如何比较两个的大小上面做优化(当时有点脑抽筋,想到以前见过的不用if,?:,switch来比较两个数的大小int array = {a, b}, int max = array max) { max = array; } if (array < min) { min = array; } } printf("max = %d, min = %d\n", max, min); return 0; }   还有个题目是去除一个数组中的重复元素,列如下面的数组得到 array = {2, 3, 1, 2, 1, 1, 4, 4, 5, 1}; //得到这样的结果 array = {2, 3, 1, 4, 5} 我在写的时候我用的是统计法,先找出数组中的最大数,然后用这个最大数来申请一个新的空间(时间复杂度是n)。考官说我的算法浪费空间,而且非整数不可用,这里我就不写我的实现了,写一个我回来写的实现 #include #include /* 表示数组这个数有重复存在 */ #define EXIST 2147483647 int main(int argc, char *argv) { int array = {2, 3, 1, 2, 1, 1, 4, 4, 5, 1};...
阅读全文