编程题：小明的筷子

小明是个马大哈，某天他到超市买了若干双筷子(n 小于 20)
筷子的长度不尽相同，他把全部筷子都放在购物袋里面拿回家，路上不小心漏了一根
请你用程序帮他找出漏掉的筷子是多长的。

输入：

参数一：剩下的筷子的长度值的数组，例如：1, 2, 3, 2, 1, 3, 2，(筷子的长度必然大于0, 不需要校验)

参数二：数组的元素的数量；
返回值：漏掉的筷子的长度，如上述输入返回：2

当输入的筷子数据异常时返回-1，如：找不到漏掉的筷子

如果漏掉了多根筷子，返回任意一根漏掉的筷子即可。

这个题目有点容易误解的地方就是：n小于20，n到底是n双，还是n根。
加入按照n是n根来答题，我写了如下的代码，总是有2,3个测试案例过补了，还请指教。

#include "CheckChopsticks.h"


/*
小明是个马大哈，某天他到超市买了若干双筷子（n < 20）
筷子的长度不尽相同，他把全部筷子都放在购物袋里面拿回家，路上不小心漏了一根
请你用程序帮他找出是漏掉的筷子是多长的。

输入：  剩下的筷子数组，如：1, 2, 3, 2, 1, 3, 2
返回值：漏掉的筷子长度，如上述输入返回：2（当输入的筷子数据异常时返回-1，如：找不到漏掉的筷子）

*/
int checkChopsticks(int chopsticks[], int arraySize)
{
	int i,j,count = 0;
	int found = 0;
	int firstFound = -1;

	if (arraySize >= 20 || arraySize <= 0)
		return -1;

    for(i = 0; i < arraySize && 0 != chopsticks[i]; i ++)
	{
		for(j = i + 1; j < arraySize; j++)
		{
			if(chopsticks[i] == chopsticks[j])
			{
				chopsticks[i] = chopsticks[j] = 0;
				count++;
				break;
			}
		}
	}

	//找不到漏掉的筷子
	if(count * 2 == arraySize)
		return -1;

	//返回找到的第一根漏掉的筷子
	for(i = 0; i < arraySize; i++)
	{
		if(0 != chopsticks[i])
		{
			if(-1 == firstFound)
				firstFound = i;
			found++;
		}
	}
	if((-1 != firstFound) && (count + found)*2 < 20)
        return chopsticks[firstFound];
    return -1;
}

12 个解决方案

#1

n双

#2

如果只漏了1根筷子，则只需要将剩余筷子的长度依次异或，结果即为漏掉的那根筷子的长度；

如果漏了k根筷子，且k>=1，那么当k为偶数时，问题可能无解。例如漏了2根筷子，且其长度相同。

#3

引用 1 楼 zhao4zhong1 的回复:

n双

能帮我分析上上面的代码有什么疏漏吗？

#4

排序+计数

#5

用数组下标存值

/*
小明是个马大哈，某天他到超市买了若干双筷子（n < 20）
筷子的长度不尽相同，他把全部筷子都放在购物袋里面拿回家，路上不小心漏了一根
请你用程序帮他找出是漏掉的筷子是多长的。
 
输入：  剩下的筷子数组，如：1, 2, 3, 2, 1, 3, 2
返回值：漏掉的筷子长度，如上述输入返回：2（当输入的筷子数据异常时返回-1，如：找不到漏掉的筷子）
 
*/
#include <stdio.h>

#define MAX_LEN 20

int find_lost_chopsticks(int a[],int num)
{
	int len[MAX_LEN+1]={0};
	int i;
	for(i=0;i< num;i++)
	{
		len[a[i]]++;
		if(len[a[i]]==2)len[a[i]]=0;
	}
	for(i=1;i<MAX_LEN+1;i++)
	{
		if(len[i])return i;
	}
	return -1;
}

int main()
{
	int a[]={1, 2, 3, 2, 1, 3, 2};
	printf("%d\n",find_lost_chopsticks(a,sizeof(a)/sizeof(int)));
	return 0;
}

#6

试改2行:

  for(i = 0; i < arraySize; i ++) //改 for(i = 0; i < arraySize && 0 != chopsticks[i]; i ++)
  {
    if(0 != chopsticks[i]) for(j = i + 1; j < arraySize; j++) //改 for(j = i + 1; j < arraySize; j++)
    {
      if(chopsticks[i] == chopsticks[j])
      {
        chopsticks[i] = chopsticks[j] = 0;
        count++;
        break;
      }
    }
  }

#7

若筷子不是金箍棒一样长的话用位图法再简单不过了判断是奇数的就是少了的一跟筷子了编程题：小明的筷子

#8

你这个输入固定了和题目要求不符吧

#9

我怎么没看懂，怎么漏掉的？查找的规则是什么？

#10

哦，明白了明白了，原来是一系列数不能组成对的多出来的那根啊

#11


int tmp[SIZE]={}
for(int i=0;i<Input.length;i++)
{
      tmp[i]++;
}

for(int i=0;i<SIZE;i++)
{
     if(tmp[i]==1)
     {
           //find
     }
}

这是伪代码，大家看看如何？

#12

当数组中出现元素0的时候，表示数量错误，返回-1
当数组中，有两个以上奇数个统一长度的筷子时候，表示漏掉不止一根，返回第一个奇数个的长度好了
当筷子全部成对的时候，表示没有漏掉，或者出错，返回 -1

#1

n双

#2

#3