一貧如洗的樵夫阿里巴巴在去砍柴的路上，無意中發(fā)現(xiàn)了強(qiáng)盜集團(tuán)的藏寶地，藏寶地有編號(hào)從0~N的箱子，每個(gè)箱子上面貼有箱子中藏有金幣的數(shù)量。

從金幣數(shù)量中選出一個(gè)數(shù)字集合，并銷毀貼有這些數(shù)字的每個(gè)箱子，如果能銷毀一半及以上的箱子，則返回這個(gè)數(shù)字集合的最小大小。

輸入描述:

一個(gè)數(shù)字字串，數(shù)字之間使用逗號(hào)分隔，例如: 6,6,6,6,3,3,3,1,1,5字串中數(shù)字的個(gè)數(shù)為偶數(shù)，并且個(gè)數(shù)>=1，<=100000; 每個(gè)數(shù)字>=1，<=100000;

輸出描述

這個(gè)數(shù)字集合的最小大小，例如: 2

示例1

輸入:

1,1,1,1,3,3,3,6,6,8

輸出:

2

說明:

選擇集合{1,8}，銷毀后的結(jié)果數(shù)組為 [3,3,3,6,6]，長度為 5，長度為原數(shù)組的一半。

大小為 2 的可行集合還有{1,3},{1,6},{3,6}。

選擇6,8 集合是不可行的，它銷毀后的結(jié)果數(shù)組為[1,1,1,1,3,3,3]，新數(shù)組長度大于原數(shù)組的二分之一。

示例2

輸入:

2,2,2,2

輸出:

1

說明:

我們只能選擇集合2]，銷毀后的結(jié)果數(shù)組為空

Java 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/130936645

Python實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/130961999

C++ 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/131023524

JavaScript實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/131080266

C實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/131006083