求救：算法问题

Question

你先sort一下
然后判断后一个数不等于前一个数时.....
关键你先排一下序。排序后就什么都可以了

Answer 1

不用这么麻烦，利用Java中的Set，比如：
<<
public int calculateDuplicateCount(int[] a) {
    Set set = new HashSet();
    for(int i=0; i<a.length; i++) {
        set.add(new Integer(a[i));
    }
    return a.length - set.size();
}
>>

Answer 2

[修正]好像和楼主的意思有点偏差，那么就这样：
<<
public int calculateDuplicateCount(int[] a) {
    Set set = new HashSet();
    Set dupSet = new HashSet();
    for(int i=0; i<a.length; i++) {
        if(set.contain(new Integer(a[i])) {
            dupSet.add(new Integer(a[i]);
        } else {
            set.add(new Integer(a[i]));
        }
    }
    return dupSet.size();
}
>>

Answer 3

做了一个单元测试(junit)，测试ok.//下面的方法没有编译错误:)
<<
public class TestA extends TestCase {
    public TestA(String name) {super(name);}    public void testCalculateDuplicateCount() {
        int[] a = {1,0,0,2,5,1,1};
        assertEquals(2, calculateDuplicateCount(a));
    }    public int calculateDuplicateCount(int[] a) {
        Set set = new HashSet();
        Set dupSet = new HashSet();
        for(int i=0; i<a.length; i++) {
            if(set.contains(new Integer(a[i]))) {
                dupSet.add(new Integer(a[i]));
            } else {
                set.add(new Integer(a[i]));
            }
        }
        return dupSet.size();
    }
}
>>

Answer 4

遍历原数组，将值相同的元素add进同一个Vector，这样每一个Vector里的元素都是相同的，在把每个Vector还原成数组就ok了

Answer 5

TO:xiaohaiz(老土进城,两眼通红)既然要用if(set.contains(new Integer(a[i]))) {为什么还要用HashSet()呢直接用if(dupSet.add(new Integer(a[i]))) {怎么样^_^

Answer 6

TO binny(骑个破车看夕阳) :
恕俺才疏，如何修正可保证单元测试通过？
<<
    public int calculateDuplicateCount(int[] a) {
        Set set = new HashSet();
        Set dupSet = new HashSet();
        for(int i=0; i<a.length; i++) {
            if(set.contains(new Integer(a[i]))) {
                dupSet.add(new Integer(a[i]));
            } else {
                set.add(new Integer(a[i]));
            }
        }
        return dupSet.size();
    }>>

Answer 7

TO binny(骑个破车看夕阳):
如果只有一个Set，那么只能取到有多少个重复的数字。
如果修正如下：
<<
    public int calculateDuplicateCount(int[] a) {
        int result = 0;
        Set dupSet = new HashSet();
        for(int i=0; i<a.length; i++) {
            if(!dupSet.add(new Integer(a[i]))) {
                result ++;
            }
        }
        return result;
    }
>>
这和俺在二楼贴出的做法就有异曲同工之效了。
但是楼主的需求中实际上数字可能重复多次的，比如有三个1，但是算重复只能算作一个。因此俺使用dupSet来标示发现重复的数字，之所以选择使用HashSet，也是因为重复多次也只算一次。
因此有点没有想明白你的修正方式。应该如何做？另TO Shrewdcat(丧邦&灵猫&潇):
2重循环遍历和一个中间变量，恐怕没有这么简单。你实现看看，恐怕逻辑会比较复杂的。:)

Answer 8

我看的有点糊涂了，自己简单的想应该是新建一个list
遍历数组，如果在list中没有的，就list.add，如果有就跳过
最后看list.count(?或者.length）应该很明白吧，如果重复率很高的话，应该效率最高的吧

Answer 9

加条广告(注:如果你不高兴,可以删除)
招聘JSP网页编程人员(1-2名)
1-2年的网页编程经验
语言:JSP,java,html,javascript
请在简历中写明对以上语言的掌握程度以及学历.北京友联创新系统集成有限公司
联系方式:
010-62984859-8010王先生
[email protected]

Answer 10

算法真是丰富，呵呵。俺的一位朋友写下了如下的算法，单元测试也PASS：
<<
    public int calculateDuplicateCount(int[] a) {
        Map map = new HashMap();
        for(int i=0; i<a.length; i++) {
            Integer each = new Integer(a[i]);
            if(map.containsKey(each)) {
                map.put(each, Boolean.valueOf(true));
            } else {
                map.put(each, Boolean.valueOf(false));
            }
        }
        int result = 0;
        for(Iterator it=map.values().iterator();it.hasNext();) {
            if(((Boolean)it.next()).booleanValue()) result++;
        }
        return result;
    }>>

Answer 11

另一位朋友又一种方式：
<<
    public int calculateDuplicateCount(int[] a) {
        Map counts = new HashMap();
        for (int i = 0; i < a.length; i++) {
            Integer ele = new Integer(a[i]);
            Integer value = (Integer) counts.get(ele);
            if (value != null) {
                counts.put(ele, new Integer(value.intValue() + 1));
            } else {
                counts.put(ele, new Integer(1));
            }
        }
        counts.values().removeAll(Arrays.asList(new Integer[]{new Integer(1)}));
        return counts.values().size();
    }
>>

Answer 12

由于数组中最大的值是9，我朋友的算法如下：
int[] counters=new int[10];
for(int i=0;i<a.length;i++)
{
  counters[a[i]]++;
} 
int j=0;
for(int i=0;i<counters.length;i++)
{
  if(counters[i]>=2)
  {
j++;
  }
}
return j;他说：new Integer(a[i])很耗时间的；
谢谢各位的帮助！！！