This topic has been archived. It cannot be replied.
-
工作学习 / 学科技术讨论 / 请教C＋＋高手帮回答２个题。。先谢了1. You are given an unsorted, two dimensional, array containing unique pixel coordinate values between (1..X, 1..Y). However, somewhere in the array there is a single missing coordinate pair within the defined range. Write a function that takes this array as a parameter and returns the missing coordinate.
2.Discuss how your function would have to be modified to support an array containing two missing
-victroy(网管);
2011-1-25
{408}
(#6476850@0)
-
Please define "missing coordinate pair" first
-wangqingshui(忘情水);
2011-1-25
(#6476856@0)
-
doesn't matter, 我人为可以自己define them in code, thanks
-victroy(网管);
2011-1-25
(#6476863@0)
-
我是说我没明白什么叫“missing coordinate pair”
-wangqingshui(忘情水);
2011-1-25
(#6476933@0)
-
(1,10), (2,11),(4,13) missing (3, 12)
-c1xwy(洪兴罩俺去战斗);
2011-1-25
(#6476945@0)
-
首先我不是高手。第一题可以当数学题解（如果座标个数不多的话），把所有的横坐标求和得A，再对1-X求和得B，(B-A)就是missing的横座标。如果横座标多次出现，方法也类似。
-collapsar(笨笨和旦旦+Emma);
2011-1-25
(#6476967@0)
-
和C++没关系. 对于这种知道范围的特别是连续的用BUCKET SORT最快.
-bully2007(2007);
2011-1-25
(#6476989@0)
-
谢谢了上面几位，我也是觉得只是算法问题而非programming language问题，。。good night
-victroy(网管);
2011-1-25
(#6477023@0)
-
Although it’s an algorithm question, LINQ (.NET) has build-in function Except. It's like SQL EXCEP (SQL server and db2) / MINUS (Oracle) operator.Missing_X_elements = Full_X_elements.Except(X_elements)
-deep_blue(BLUE);
2011-1-30
{55}
(#6484285@0)
-
There is equivalence in C++ too: algorithm set_difference in STL.
-wangqingshui(忘情水);
2011-1-30
(#6484470@0)
-
Hoever, set minus operation and sorting mentioned in above replies all require sorting the 2 dimentional array (1..X, 1..Y) and the time cost is O(X*Y *Log(X*Y)). From my point of view,the cost is too high.
-wangqingshui(忘情水);
2011-1-30
(#6484479@0)
-
Too complicated by C++.In LINQ, it's very easy to get X only list from (X, Y) list.
LINQ except method can be used in one, two, three, .. dimension list. Using in one dimension list, it applies default equal (compare) implemetation.
In two or more dimension, you just need do one more thing, defining a equal (compare) implemetation.
-deep_blue(BLUE);
2011-1-30
{318}
(#6484536@0)
-
The following approach resolves the questions 1 & 2 with time cost O(X*Y) and I believed it's the optimal algorithm.Suppose the original array is pair<int, int> pixel(x,y). we can define a boolean/bit array flag(x, y) with intial values false or 0.
for each pixel(i, j), set flag(pixel(i, j).key, pixel(i, j).value) = true or 1. Then loop through flag array to find the elements with false or 0 values whose indexes are missing in the original array.
The time cost is O(X*Y). This resolve question 2 as well.
-wangqingshui(忘情水);
2011-1-30
{400}
(#6484483@0)
-
用bit map。
-majorhomedepot(马甲后的炮);
2011-1-30
(#6484498@0)
-
鄙人来献献丑，说得不对，欢迎诸位雅正。鄙人认为，这两题可视为智力测试题。题分析透了，用不用C++就无关紧要了。
-perryuan(perryuan);
2011-1-31
(#6486788@0)
-
第一题：有一个两维数组，不妨记为Ａ。数组Ａ的成员的值，是象素座标值（ａ，ｂ），其中１≤ａ≤Ｘ，１≤ｂ≤Ｙ。显然，这样的象素座标值，总共有ＸＹ个。
-perryuan(perryuan);
2011-2-6
(#6486797@0)
-
要点是，这样的象素座标值是唯一的（unique），即每个象素座标值在Ａ中至多出现一次。
-perryuan(perryuan);
2011-2-6
(#6486801@0)
-
为了方便讨论问题，我来作个一一对应：把象素座标值（１，１），（１，２），……，（１，Ｙ），（２，１），（２，２），……，（Ｘ，Ｙ）映射成正整数１，２，……，Ｙ，Ｙ＋１，Ｙ＋２，……，ＸＹ。公式是很简单的，略去了。
-perryuan(perryuan);
2011-2-6
(#6486814@0)
-
Bravo! Beautiful. BTW, what's "空间复杂性"?
-cca(不归的如来佛);
2011-2-6
(#6494342@0)
-
Time complexity & space complexity
-wangqingshui(忘情水);
2011-2-6
(#6494344@0)
-
现在可以说，数组Ａ的成员的值是正整数，范围从１至ＸＹ，每个这样的正整数在Ａ中至多出现一次。但是，这样的正整数有一个没有在数组Ａ的成员中出现。问题一就是要找出这个missing的数字。
-perryuan(perryuan);
2011-1-31
(#6486824@0)
-
举个例子，Ｘ＝３，Ｙ＝２，故ＸＹ＝６。若数组Ａ的成员中有数字６，３，１，５，４，则missing的那个数字是２。
-perryuan(perryuan);
2011-1-31
(#6486835@0)
-
现在处理一下编程的技术细节：那么数组Ａ总共有多少个成员呢？至少要有ＸＹ－１个。如果多于ＸＹ－１个，那么多于ＸＹ－１个那些成员应该放入数字０。
-perryuan(perryuan);
2011-1-31
(#6486859@0)
-
问题一的解法：把数组Ａ中的全部成员的值相加，得到的和，与（ＸＹ）（ＸＹ＋１）／２相比较，就可知道缺了哪个数字。
-perryuan(perryuan);
2011-2-1
(#6486863@0)
-
这个算法，时间复杂性Ｏ（ＸＹ），空间复杂性Ｏ(１)。易知是最优的算法。
-perryuan(perryuan);
2011-2-1
(#6486869@0)
-
问题二问的是：如果缺少了两个数字，如何在问题一算法的基础上作些修改，求出这两个缺少的数字。
-perryuan(perryuan);
2011-2-1
(#6486872@0)
-
如果缺少的是两个数字（假定是ｘ和ｙ），那么算法一得到的是ｘ＋ｙ。
-perryuan(perryuan);
2011-2-1
(#6486874@0)
-
令ｚ＝（ｘ＋ｙ）／２（truncate）。简单的结论是ｘ和ｙ中至少有一个数字在１和ｚ之间。
-perryuan(perryuan);
2011-2-1
(#6486877@0)
-
于是，再扫描一遍数组Ａ，把所有小于等于ｚ的数字加起来，与ｚ（ｚ＋１）／２相比较，可以得到ｘ和ｙ中较小的那一个。从已知的ｘ＋ｙ，可以得到另一个。
-perryuan(perryuan);
2011-2-1
(#6486881@0)
-
算法二（两遍扫描）的复杂性同算法一。（完了。）
-perryuan(perryuan);
2011-2-1
(#6486883@0)