在由N个正整数的集合S中:找出最大元素,满足C=A+B,其中A,B都是集合S中元素。请给出算法描述、代码与时间复杂度分析。

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055

asked 14 Sep '14, 18:18

www%E7%82%B921qa%E7%82%B9net's gravatar image

www点21qa点net
717813

编辑于 16 Sep '14, 09:12

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116

这道题非常火,最近很多从搜索引擎过来的链接,只可惜百度给收录错了,只收录了主页,还是IP地址形式。

(21 Sep '14, 18:55) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

方法一

遍历集合

伪代码:

for c in S:
    for a in S:
        for b in S:
            if c == (a + b):
                compare (c, a, b) with last (c, a, b)
                store (c, a, b) in max

print max

注意:以上伪代码未考虑元素重复的情形。

时间复杂度O(n^3)

若是采用这种解法,BAT(Baidu, Alibaba, Tencent)是进不去了!而且会被鄙视得不行。

方法二

sort(S)                排序,逆序
cb = combination(S)    输出组合 
mcb = map(cb)          以组合中的元素和即(a+b)作为key建map

for c in S:
   if e = search(mcb,c):
       that's it, print the element e
       return

when goes here, means no solution

时间复杂度分析:

  • 排序,选一个好点的方式。

    O(n*logn)

  • 输出组合? 暂且认为是这个吧~

    O(C(n,2))

  • 建map,此处m为C(n,2),即组合个数。

    O(m*logm)

  • 遍历

    O(n)

  • 判断

    O(logm)

总的时间复杂度:

O(n*logn) + O(m)  + O(m*logm) + O(n*logm)    其中m=C(n,2)

看起来挺复杂,但是可以肯定,其小于O(n^3)这个级别,应该也小于O(n^2)这个级别吧,谁的数学好,可以分析下?

我是业余的,不知道我算错了没有,若有错,其他人来修正吧~

方法三

或许有其它的巧解?没有研究过,留待他人补充。

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link
This 回答 is marked "community wiki".

answered 17 Sep '14, 17:07

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link: [text](http://url.com/ "title")
  • image: ![alt](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×33
×14

question asked: 14 Sep '14, 18:18

question was seen: 5,505 times

last updated: 21 Sep '14, 18:55

powered by O*S*Q*A

粤ICP备14040061号-1