簡單的算法 ： 求兩個數組的不同。
已知，有兩個數組，已排序，但可能不等長，要求列出其不相同的元素，
比如：
1。A = { 1,2,3,4 } <--> B = { 1,2,3 }
2。A = { 1,3,4 } <--> B = { 1,2,3,5 }
3。 A = { 1 } <--> B = { 1,2,3,4,5}
結果：
1, 4 --> ?
2, ???? ---> 2
4 ---> ????
???? ---> 5
3, ?????--->2
??? --->3
??? --->4
??? --->5
因為數組很大，要求時間最短。
问题点数：100、回复次数：10Top
1 楼honker110（honker）回复于 2006-12-01 12:02:28 得分 10
int main()
{
int a[] = { 1, 3, 4, 5, 7, 8 };
int b[] = { 1, 2, 3, 4, 6, 7 };
int m = sizeof(a) / sizeof(int);
int n = sizeof(b) / sizeof(int);
int x = 0;
int y = 0;
while ( x < m - 1 || y < n - 1 )
{
if (a[x] > b[y])
{
printf("??? -> %d\n", b[y]);
if (y < n - 1)
y++;
}
else if (a[x] == b[y])
{
if (x < m - 1)
x++;
if (y < n - 1)
y++;
}
else if (a[x] < b[y])
{
printf("%d -> ???\n", a[x]);
if (x < m - 1)
x++;
}
}
}
Top
2 楼HappyTree（笨笨·天行健）回复于 2006-12-01 12:20:19 得分 10
#include <iostream>
using namespace std;
void Compare(int* a1, int l1, int* a2, int l2)
{
int i = 0, j = 0;
while (i < l1 && j < l2)
{
if (a1[i] < a2[j])
{
cout << a1[i++] << " ";
}
else if (a1[i] > a2[j])
{
cout << a2[j++] << " ";
}
else
{
i++;
j++;
}
}
for (; i < l1; i++)
{
cout << a1[i] << " ";
}
for (; j < l2; j++)
{
cout << a2[j] << " ";
}
}
int main()
{
int a1[] = {1, 2, 4, 5, 6, 8, 9};
int a2[] = {1, 2, 6};
Compare(a1, sizeof(a1) / sizeof(int), a2, sizeof(a2) / sizeof(int));
return getchar();
}Top
3 楼OufengMorpheus（欧阳锋）回复于 2006-12-01 12:23:00 得分 0
分几种情况
两数组没有重叠元素，
两数组有重叠元素：
1，两数组等长，并完全重叠。
2，两数组不等长，其中一数组是另一数组的子集。
3，上述两种情况以外，
分析好规律，才能提高速度。
另，输入一数据处理一数据。不要准备全部输入完后一起处理。
题目描述和测试数据都很简单，很容易迷惑人。但是这类题并不简单。可能有很多很好的很简单算法。看您的创造力啦，
江泽民同志说：“要与日俱进”“要创新”，，越来越觉得有道理。
Top
4 楼sclzmbie（忘我）回复于 2006-12-01 12:40:43 得分 5
这么简单的问题，用不着扯太远吧！ 天行键的程序就不错。Top
5 楼greenteanet（扎扎实实打基础，保持一颗平常心。）回复于 2006-12-01 12:55:36 得分 10
#include <iostream>
using namespace std;
void Compare(int* a1, int l1, int* a2, int l2)
{
int i = 0, j = 0;
while (i < l1 && j < l2)
{
if (a1[i] < a2[j])
{
cout << a1[i++] << " -> ???" << endl;
}
else if (a1[i] > a2[j])
{
cout << "??? -> "<< a2[j++] << endl;
}
else
{
i++;
j++;
}
}
for (; i < l1; i++)
{
cout << a1[i] << " -> ???" << endl;
}
for (; j < l2; j++)
{
cout << "??? -> "<< a2[j] << endl;
}
}
int main()
{
int a1[] = {1, 2, 4, 5, 6, 8, 9};
int a2[] = {1, 2, 3, 6};
Compare(a1, sizeof(a1) / sizeof(int), a2, sizeof(a2) / sizeof(int));
cout << endl;
int a3[] = {1};
int a4[] = {1, 2, 4};
Compare(a3, sizeof(a3) / sizeof(int), a4, sizeof(a4) / sizeof(int));
return getchar();
}Top
6 楼taodm（（不能收CSDN社区短信息，请莫浪费精力））回复于 2006-12-01 13:08:32 得分 65
STL里已经有现成的了，set_difference
打开源码抄抄就是了，才11行。Top
7 楼greenteanet（扎扎实实打基础，保持一颗平常心。）回复于 2006-12-01 13:19:58 得分 0
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2)
if (*first1 < *first2) {
*result = *first1;
++first1;
++result;
}
else if (*first2 < *first1)
++first2;
else {
++first1;
++first2;
}
return copy(first1, last1, result);
}
template <class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp) {
while (first1 != last1 && first2 != last2)
if (comp(*first1, *first2)) {
*result = *first1;
++first1;
++result;
}
else if (comp(*first2, *first1))
++first2;
else {
++first1;
++first2;
}
return copy(first1, last1, result);
}
Top
8 楼tree2000（NewBuilder）回复于 2006-12-01 14:44:19 得分 0
To OufengMorpheus(欧阳锋) ( ) 信誉：100 Blog ,
我的需求是：
無重復，已排序，不等長，求不同。
江泽民同志不是程序員，他說的話對這個算法沒有用。
我只要結果，你怎樣分析就怎樣。既然你這麼會分析，怎麼不貼一段代碼出來？我還知道物質決定意識呢！
Top
9 楼tree2000（NewBuilder）回复于 2006-12-01 14:49:42 得分 0
我個人比較喜歡 “taodm(taodm) ( ) 信誉：100 Blog ”。
不想重復地發明輪子。Top
10 楼OufengMorpheus（欧阳锋）回复于 2006-12-02 15:27:08 得分 0
不好意思，我以为你是为了参加ACM/ICPC的问题，理解错误。
楼上的回答的很好。很有内涵。Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
