算法设计 木棒问题.ppt

木棒问题 张子臻 给出nn为奇数根木棒其中有(n-1)/2对木棒的长度是相同的只有一根木棒的长度是不成对的要求找出这根木棒 有长度1到长度n共n根木棒现从中拿走某一根再放入一根任意长度的木棒输入这n根木棒的长度求拿走与放入木棒的长度分别是多少 有n根木棒其中有多于一半的木棒其长度相等求该木棒的长度是多少 要求时间复杂度O(n)空间复杂度O(1) 将所有木棒的长度异或起来得到的结果即为不成对那根木棒