hao爱做网站,做网站的怎么赚钱,wordpress文章添加忽略,山东建设主管部门网站题目 设计算法并写出代码移除字符串中重复的字符#xff0c;不能使用额外的缓存空间。注意#xff1a; 可以使用额外的一个或两个变量#xff0c;但不允许额外再开一个数组拷贝。 进一步地#xff0c; 为你的程序写测试用例。 解答 这道题目其实是要你就地(in place)将字符…题目 设计算法并写出代码移除字符串中重复的字符不能使用额外的缓存空间。注意 可以使用额外的一个或两个变量但不允许额外再开一个数组拷贝。 进一步地 为你的程序写测试用例。 解答 这道题目其实是要你就地(in place)将字符串中重复字符移除。你可以向面试官问清楚 不能使用额外的一份数组拷贝是指根本就不允许开一个数组还是说可以开一个固定大小 与问题规模(即字符串长度)无关的数组。 如果根本就不允许你再开一个数组只能用额外的一到两个变量。那么你可以依次访问 这个数组的每个元素时间复杂度为O(n2 )代码如下 #includeiostream
#includecstring
using namespace std;void removeDuplicate(char *str)
{if(strNULL)return;int count0;int nstrlen(str);for(int i1;in;i){int ji-1;while(j0){if(str[i]str[j]){count;break;}else--j;}if(j0)str[i-count]str[i];}str[n-count]\0;
}int main()
{char str[];removeDuplicate(str);coutstrendl;
} 如果可以开一个固定大小与问题规模(即字符串长度)无关的数组那么可以用一个数组来 表征每个字符的出现(假设是ASCII字符则数组大小为256)这样的话只需要遍历一遍字符 串即可时间复杂度O(n)。代码如下 void removeDuplicate(char s[])
{int len strlen(s);if(len 2) return;bool c[256];memset(c, 0, sizeof(c));int p 0;for(int i0; i len; i){if(!c[s[i]]){s[p] s[i];c[s[i]] true;}}s[p] ;
} 转载于:https://www.cnblogs.com/wuchanming/p/4447792.html
