java 中 统计出 数组中 相同的数字 和字符串

Question

要求 找出 数组（Array）中 相同的数字个数 时间复杂度为 O（n）
要求 找出 数组（Array）中 相同的字符串个数 时间复杂度为 O（nlogn）
只要提供大概的思路就好
谢谢了
例如 数组 为 {1,8,5,2,1,6,2,9,8} 相同数字个数为 6
数组 为 {ab,bv,cd,sv,ab,cd} 相同字符串个数为 4
字符串问题已经解决，求数字问题的算法 符合要求的追加 35分
刚学 数据结构不久 希望说得明白点 对于api 还不是很熟悉

Answer 1

首先，用java中的有序的Array，你根据自己需要重写compare方法，第一个问题就是按照数字的大小排序，第二就是按照字符个数排序（有序的Array在建立过程中已经正确排序了），这样就得到两个有序数组。

第二，太简单了，自己思考吧。一个循环搞定，复杂度O（n）。

排序复杂度也是O(n)，所以这两个题复杂度都是O（n）

Answer 2

汗。楼上的有没有搞错啊，你那是去重，楼主是要找出重复的个数，真晕

给你个思路，首先定义个int，然后循环，拿数组中的第一个和数组中的所有比，有一样的，从数组中将那个一样的删除，并int加1，全部比完后int再加1，然后再拿数组中的第二个和数组中的所有比，直到完。

差不多就这么个思路，具体细节没有细考虑，交给楼主自己吧

我自己想的，不知道对不对，呵呵本回答被提问者和网友采纳

Answer 3

2楼的方法很好。
使用MAP也不错，一下可以定位到是否有相同数字。

Answer 4

这里有一篇时间复杂度的文章 你看看http://www.85java.com/viewthread.php?tid=941

Answer 5

弄个Set就好了
int[] array={1,8,5,2,1,6,2,9,8};
for(int num:array)
{
set.add(num);
}
System.out.println(set.size());
set自动去重

RE: 136234058
重复的个数不就是array.length-set.size();
这种问题还需要别人解释吗