一道面试题，求更好的答案

题目：数组中有重复数据，求出每个数据出现的次数并按照次数的由大到小排列出来

我是用 二维数组做的，有没有更好的答案

public static void main(String[] args) {
		int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
				3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
				7, 8, 8, 7, 8, 7, 9, 0 };

		int array2[][] = new int[array.length][2];
		for (int i = 0; i < array.length; i++) {
			int count = 1;
			if (array[i] != -100) {
				for (int j = i + 1; j < array.length; j++) {
					if (array[i] == array[j]) {
						array[j] = -100;
						count++;
					}
				}
				array2[i][0] = array[i];
				array2[i][1] = count;
			}
		}
		//冒泡排序
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = 0; j < array.length - i - 1; j++) {
				int temp[] = new int[2];
				if (array2[j][1] < array2[j + 1][1]) {
					temp = array2[j];
					array2[j] = array2[j + 1];
					array2[j + 1] = temp;
				}
			}
		}

		for (int i = 0; i < array.length; i++) {
			if (array2[i][1] != 0)
				System.out.println(array2[i][0] + "---------" + array2[i][1]);
		}
	}

93 个解决方案

#1

数字都很小，最小到最大只不过是 0～9

所以统计过程可以简化为只需要一个 一维数组来完成：
int[] count = new int[10];
for (int i = 0;i<array.length;i++) {
    count[array[i]]++;
}

#2

引用 1 楼 ldh911 的回复:

数字都很小，最小到最大只不过是 0～9

所以统计过程可以简化为只需要一个 一维数组来完成：
int[] count = new int[10];
for (int i = 0;i<array.length;i++) {
    count[array[i]]++;
}

谢谢，学习了

#3

改变你的数据存储方式，不要仅仅局限于for循环、冒泡之类的线性算法，并且把“面向”对象的思想融入编程。
以下方法，算法的平均复杂度为O(Nlog2N)。
中心思想：遍历数组，依次插入到二叉排序树，如果找到数字相等的，节点的count++；中序遍历算法，输出这个二叉排序树。（PS：如果想得到标准的O(Nlog2N)算法，可以通过旋转树枝的办法，减小树的高度，把二叉排序树优化为平衡二叉树。）
节点类：

package tm.cao.sort;

/**
 * 节点类
 *
 */
public class TreeNode {

/**
 * 关键字
 */
private int data;

/**
 * 左子树
 */
private TreeNode leftCh;

/**
 * 右子树
 */
private TreeNode rightCh;

/**
 * 关键字出现的次数 
 */
private int count;
public int getData() {
	return data;
}
public TreeNode getLeftCh() {
	return leftCh;
}
public TreeNode getRightCh() {
	return rightCh;
}
public int getCount() {
	return count;
}
public void setData(int data) {
	this.data = data;
}
public void setLeftCh(TreeNode leftCh) {
	this.leftCh = leftCh;
}
public void setRightCh(TreeNode rightCh) {
	this.rightCh = rightCh;
}
public void setCount(int count) {
	this.count = count;
}
public TreeNode(int data) {
	super();
	this.data = data;
	this.count=1;
}
public TreeNode(int data, TreeNode leftCh, TreeNode rightCh) {
	super();
	this.data = data;
	this.leftCh = leftCh;
	this.rightCh = rightCh;
	this.count = 1;
}
public TreeNode() {
	super();
}

/* 为了便于调试和输出  生成toString()
 */
@Override
public String toString() {
	return "数字=" + data + ", 出现次数=" + count + "";
}

}

二叉排序树的类：

package tm.cao.sort;

import org.junit.Test;

/**
 * 二叉排序树的类
 *
 */
public class TreeInsert {

/**
 * 根节点
 */
private TreeNode root;

public TreeNode getRoot() {
	return root;
}

public void setRoot(TreeNode root) {
	this.root = root;
}

/**
 * 总的方法
 */
public void createTreeAndOutPut(int[] array){
	//只需遍历一次数组 遍历的同时插入节点到排序树
	for(int data:array){
		this.insertNode(data);
	}
	//中序输出这个排序树
	this.middleOrder(root);
}

/**
 * 中序遍历 递归算法 p为当前节点的指针
 */
public void middleOrder(TreeNode p){
	if(p!=null){
		//遍历左子树
		this.middleOrder(p.getLeftCh());
		//遍历本次节点
		System.out.println(p);
		//遍历右子树
		this.middleOrder(p.getRightCh());
	}
}
/**
 * 插入单个节点的方法
 */
public void insertNode(int data){
	//如果没有根节点 创造新的根节点
	if(this.getRoot()==null){
		root=new TreeNode(data);
	}else{
		//初始化指针p指向根节点
		TreeNode p=root;
		while(true){
			//如果p的data小于data  
			if(p.getData()<data){
				//如果p没有左子树  则直接插入到p的左子树
				if(p.getLeftCh()==null){
					TreeNode leftCh=new TreeNode(data);
					p.setLeftCh(leftCh);
					break;
				}else{
					//如果p有左子树 则让指针指向p的左子树 继续遍历
					p=p.getLeftCh();
					continue;
				}
			}
			//插入右子树的情况 和左子树类似
			else if(p.getData()>data){
				if(p.getRightCh()==null){
					TreeNode rightCh=new TreeNode(data);
					p.setRightCh(rightCh);
					break;
				}else{
					p=p.getRightCh();
					continue;
				}
			}else{
				//设置重复的情况  不必插入新的节点，直接让p的count加1
				int count=p.getCount();
				count++;
				p.setCount(count);
				break;
			}
		}
	}
}

/**
 * 用于测试的类  为了程序的健壮性，我们多生成些随机数放入数组
 */
@Test
public void test(){
	TreeInsert ti=new TreeInsert();
	int[] array={3,47,43,73,86,36,96,47,36,61,46,99,69,81,62,97,74,24,67,62,42,81,14,57,20,42,53,32,37,32,16,76,2,27,66,56,50,26,71,7,32,90,79,78,53,12,56,85,99,26,96,96,68,27,31,5,3,72,93,15,55,59,56,35,64,38,54,82,46,22,31,62,43,9,90};
	ti.createTreeAndOutPut(array);
}
}

#4

程序的运行结果：
数字=99, 出现次数=2
数字=97, 出现次数=1
数字=96, 出现次数=3
数字=93, 出现次数=1
数字=90, 出现次数=2
数字=86, 出现次数=1
数字=85, 出现次数=1
数字=82, 出现次数=1
数字=81, 出现次数=2
数字=79, 出现次数=1
数字=78, 出现次数=1
数字=76, 出现次数=1
数字=74, 出现次数=1
数字=73, 出现次数=1
数字=72, 出现次数=1
数字=71, 出现次数=1
数字=69, 出现次数=1
数字=68, 出现次数=1
数字=67, 出现次数=1
数字=66, 出现次数=1
数字=64, 出现次数=1
数字=62, 出现次数=3
数字=61, 出现次数=1
数字=59, 出现次数=1
数字=57, 出现次数=1
数字=56, 出现次数=3
数字=55, 出现次数=1
数字=54, 出现次数=1
数字=53, 出现次数=2
数字=50, 出现次数=1
数字=47, 出现次数=2
数字=46, 出现次数=2
数字=43, 出现次数=2
数字=42, 出现次数=2
数字=38, 出现次数=1
数字=37, 出现次数=1
数字=36, 出现次数=2
数字=35, 出现次数=1
数字=32, 出现次数=3
数字=31, 出现次数=2
数字=27, 出现次数=2
数字=26, 出现次数=2
数字=24, 出现次数=1
数字=22, 出现次数=1
数字=20, 出现次数=1
数字=16, 出现次数=1
数字=15, 出现次数=1
数字=14, 出现次数=1
数字=12, 出现次数=1
数字=9, 出现次数=1
数字=7, 出现次数=1
数字=5, 出现次数=1
数字=3, 出现次数=2
数字=2, 出现次数=1

#5

引用 3 楼 SmallYamateh 的回复:

改变你的数据存储方式，不要仅仅局限于for循环、冒泡之类的线性算法，并且把“面向”对象的思想融入编程。
以下方法，算法的平均复杂度为O(Nlog2N)。
中心思想：遍历数组，依次插入到二叉排序树，如果找到数字相等的，节点的count++；中序遍历算法，输出这个二叉排序树。（PS：如果想得到标准的O(Nlog2N)算法，可以通过旋转树枝的办法，减小树的高度，把二叉排序树……

碉堡了

#6

引用 3 楼 SmallYamateh 的回复:

改变你的数据存储方式，不要仅仅局限于for循环、冒泡之类的线性算法，并且把“面向”对象的思想融入编程。
以下方法，算法的平均复杂度为O(Nlog2N)。
中心思想：遍历数组，依次插入到二叉排序树，如果找到数字相等的，节点的count++；中序遍历算法，输出这个二叉排序树。（PS：如果想得到标准的O(Nlog2N)算法，可以通过旋转树枝的办法，减小树的高度，把二叉排序树……

受教了。

#7

该回复于2012-12-07 11:23:26被管理员删除

#8

唉，都忘光了。

#9

统计各个数字出现的次数,至于排序,暂时没什么想法,都是书上那些吧

    public static HashMap<Integer, Integer> getCount(int[] source) {
        HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int i=0; i<source.length; i++) {
            count.put(source[i], count.get(source[i])==null?1:count.get(source[i])+1);
        }
        return count;
    }

#10

引用 4 楼 SmallYamateh 的回复:

程序的运行结果：
数字=99, 出现次数=2
数字=97, 出现次数=1
数字=96, 出现次数=3
数字=93, 出现次数=1
数字=90, 出现次数=2
数字=86, 出现次数=1
数字=85, 出现次数=1
数字=82, 出现次数=1
数字=81, 出现次数=2
数字=79, 出现次数=1
数字=78, 出现次数=1
数字=76, 出现次数=……

数据结构完全忘了，你太吊了

#11

该回复于2012-12-07 13:05:10被管理员删除

#12

3楼的MM厉害啊，不但算法熟，面向对象的精髓也理解的透，佩服，佩服！

#13

请问 #9 的方法 如何解决排序问题？

#14

9楼的HashMap换成TreeMap就行了 
TreeMap是个红黑树吧，我记得。

#15

int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8, 8, 7, 8, 7, 9, 0 };
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i:array){
if (map.containsKey(i)){
map.put(i, map.get(i)+1);
}else{
map.put(i, 1);
}
}
//map按值排序
List<Map.Entry<Integer,Integer>> list = new ArrayList<Map.Entry<Integer,Integer>>(map.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {   
    public int compare(Map.Entry<Integer, Integer> o1,   
            Map.Entry<Integer, Integer> o2) {
        return ( o2.getValue()-o1.getValue());
    }
});
for(Map.Entry<Integer, Integer> m:list){
System.out.println(m.getKey()+"--"+m.getValue());
}

#16

数据结构，一定要好好学，有空我要好好看！

#17

引用 9 楼 david_li_sg 的回复:

统计各个数字出现的次数,至于排序,暂时没什么想法,都是书上那些吧
Java code?1234567    public static HashMap<Integer, Integer> getCount(int[] source) {        HashMap<Integer, Integer> count = new HashMap<Integer, Integ……

这个排序有点麻烦吧

#18

引用 15 楼 lyh_zxc 的回复:

int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8, 8, 7, 8, 7, 9, 0 };
Map<Integer,Integer> map ……

谢谢，又学到了点知识

#19

引用 15 楼 lyh_zxc 的回复:

int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8, 8, 7, 8, 7, 9, 0 };
Map<Integer,Integer> map ……

能想到集合框架固然好，但是，某些时候的笔试和面试，是禁用Java集合框架的。

#20

引用 19 楼 SmallYamateh 的回复:

引用 15 楼 lyh_zxc 的回复:
int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8, 8, 7, 8, 7, 9, 0 };
Map<Integer,Inte……

是啊，面试的时候不让使用 api 里现成的方法

#21

引用 20 楼 lct_mail 的回复:

引用 19 楼 SmallYamateh 的回复:引用 15 楼 lyh_zxc 的回复:
int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8,……

呵呵，这也和面试官有关，有的面试官考察思维，有的注重考察对API的熟悉情况，反正我感觉两方面都要练习。

#22

引用 3 楼 SmallYamateh 的回复:

改变你的数据存储方式，不要仅仅局限于for循环、冒泡之类的线性算法，并且把“面向”对象的思想融入编程。
以下方法，算法的平均复杂度为O(Nlog2N)。
中心思想：遍历数组，依次插入到二叉排序树，如果找到数字相等的，节点的count++；中序遍历算法，输出这个二叉排序树。（PS：如果想得到标准的O(Nlog2N)算法，可以通过旋转树枝的办法，减小树的高度，把二叉排序树……

想了半天也没想明白，是怎么一次遍历直接生成的二叉树。
仔细一看。。。
原来是按数的大小排序出来的，不是数字出现的次数。
竟然没人吐糟。都被这可爱的头像迷倒了吧。

#23

int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8, 8, 7, 8, 7, 9, 0 };
Arrays.sort(array); // 小到大顺序
Set<Integer> set = new HashSet<Integer>();
int setLen = 0;

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(Integer a: array) {
set.add(a);
if(set.size()>setLen) { // set长度发生变化的情况
Integer num = map.get(a);
num = (num!=null)?num:0;
map.put(a, num+1);
}
}
Iterator<Integer> it = map.keySet().iterator();
while(it.hasNext()) {
int key = it.next();
System.out.println(key+":"+map.get(key));
}

#24

引用 22 楼 gukuitian 的回复:

引用 3 楼 SmallYamateh 的回复:改变你的数据存储方式，不要仅仅局限于for循环、冒泡之类的线性算法，并且把“面向”对象的思想融入编程。
以下方法，算法的平均复杂度为O(Nlog2N)。
中心思想：遍历数组，依次插入到二叉排序树，如果找到数字相等的，节点的count++；中序遍历算法，输出这个二叉排序树。（PS：如果想得到标准的O(Nlog2N)算法，可……

好吧，你等等，哈；确实看错了题目，我再研究研究。

#25

误导大家了哈，等我再考虑考虑，我看错题目了。

#26

该回复于2012-12-08 10:26:45被管理员删除

#27

引用 3 楼 SmallYamateh 的回复:

改变你的数据存储方式，不要仅仅局限于for循环、冒泡之类的线性算法，并且把“面向”对象的思想融入编程。
以下方法，算法的平均复杂度为O(Nlog2N)。
中心思想：遍历数组，依次插入到二叉排序树，如果找到数字相等的，节点的count++；中序遍历算法，输出这个二叉排序树。（PS：如果想得到标准的O(Nlog2N)算法，可以通过旋转树枝的办法，减小树的高度，把二叉排序树……

学习

#28

对不起大家，哈；结果已经出来了，依然是二叉排序树，等我写上注释。
结果:
出现次数为13的数字有：
   2
出现次数为11的数字有：
   5
出现次数为7的数字有：
   3
出现次数为5的数字有：
   4
出现次数为3的数字有：
   6   7   8
出现次数为1的数字有：
   0   9

#29

引用 25 楼 SmallYamateh 的回复:

误导大家了哈，等我再考虑考虑，我看错题目了。

妹子。你真真误导了大家。
这群屌丝。哎。。。

妹子你真是妹子嘛？
哎。。

引用 15 楼 lyh_zxc 的回复:

int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8, 8, 7, 8, 7, 9, 0 };
Map<Integer,Integer> map ……

正解。

引用 楼主 lct_mail 的回复:

题目：数组中有重复数据，求出每个数据出现的次数并按照次数的由大到小排列出来

我是用 二维数组做的，有没有更好的答案

Java code?123456789101112131415161718192021222324252627282930313233343536public static void main(String[] args) {        in……

楼猪的也挺好的。。。。

#30

思路类似，但是复杂变大了，多了一个“以出现次数为关键字的二叉排序树”，这颗二叉排序树的节点包含两个重要信息“出现次数，一群数字的链表”。希望大家提出更快的方法。等我贴代码。

#31

第二次的二叉排序的节点：
package tm.cao.sort;

/**
 * 以“出现次数”为关键字的节点  本身包含一个链表  插入的方法为头插法
 *
 */
public class CountNode {

/**
 * 出现次数
 */
private int count;

/**
 * 链表的表头节点
 */
private SimpleNode first;

/**
 * 左子树
 */
private CountNode leftCh;

/**
 * 右子树
 */
private CountNode rightCh;
public int getCount() {
return count;
}

public CountNode getLeftCh() {
return leftCh;
}
public CountNode getRightCh() {
return rightCh;
}
public void setCount(int count) {
this.count = count;
}

public SimpleNode getFirst() {
return first;
}


public void setFirst(SimpleNode first) {
this.first = first;
}

public void setLeftCh(CountNode leftCh) {
this.leftCh = leftCh;
}
public void setRightCh(CountNode rightCh) {
this.rightCh = rightCh;
}
public CountNode(int count, SimpleNode first){
super();
this.count = count;
this.first = first;
}
public CountNode(int count) {
super();
this.count = count;
}
public CountNode() {
super();
}
@Override
public String toString() {
return "CountNode [count=" + count + "]";
}

}

#32

countNode里边的链表所包含的节点

package tm.cao.sort;

/**
 *为了计算方便，这是简单的节点类，只包含next指针和数字域
 *
 */
public class SimpleNode {

/**
 * 数字 
 */
private int data;

/**
 * 对应链表中的下一个节点
 */
private SimpleNode next;
public int getData() {
	return data;
}
public SimpleNode getNext() {
	return next;
}
public void setData(int data) {
	this.data = data;
}
public void setNext(SimpleNode next) {
	this.next = next;
}
public SimpleNode(int data) {
	super();
	this.data = data;
}
public SimpleNode() {
	super();
}
@Override
public String toString() {
	return "SimpleNode [数字=" + data + "]";
}

}

改进了一下一开始的方法，中心思想“遍历第一个二叉树的同时，向第二颗二叉排序树插叶子”

package tm.cao.sort;

import org.junit.Test;

/**
 * 二叉排序树的类
 *
 */
public class TreeInsert {

/**
 * 根节点
 */
private TreeNode root;

public TreeNode getRoot() {
	return root;
}

public void setRoot(TreeNode root) {
	this.root = root;
}

/**
 * 总的方法
 */
public void createTreeAndOutPut(int[] array){
	//只需遍历一次数组 遍历的同时插入节点到排序树
	for(int data:array){
		this.insertNode(data);
	}
	//中序遍历这个二叉排序树
	this.middleOrder(root);
	//按照出现次数输出所有数字
	middleOrderCountTree(this.getCountRoot());
}

private CountNode countRoot;


public CountNode getCountRoot() {
	return countRoot;
}

public void setCountRoot(CountNode countRoot) {
	this.countRoot = countRoot;
}

/**
 * 插入单个countNode的方法
 */
public void insertCountNode(TreeNode node){
	int count=node.getCount();
	//如果没有根节点 创造新的根节点
	if(this.getCountRoot()==null){
		countRoot=new CountNode(count);
		SimpleNode sn=new SimpleNode(node.getData());
		//设置这个链表的头结点指针
		countRoot.setFirst(sn);
	}else{
		//初始化指针p指向根节点
		CountNode p=this.getCountRoot();
		while(true){
			//如果p的data小于data  
			if(p.getCount()<count){
				//如果p没有左子树  则直接插入到p的左子树
				if(p.getLeftCh()==null){
					CountNode leftCh=new CountNode(count);
					//由于节点是新建的  所以它的链表也是空的，因此要设置链表的头指针
					SimpleNode sn=new SimpleNode(node.getData());
					leftCh.setFirst(sn);
					p.setLeftCh(leftCh);
					break;
				}else{
					//如果p有左子树 则让指针指向p的左子树 继续遍历
					p=p.getLeftCh();
					continue;
				}
			}
			//插入右子树的情况 和左子树类似
			else if(p.getCount()>count){
				if(p.getRightCh()==null){
					CountNode rightCh=new CountNode(count);
					SimpleNode sn=new SimpleNode(node.getData());
					rightCh.setFirst(sn);
					p.setRightCh(rightCh);
					break;
				}else{
					p=p.getRightCh();
					continue;
				}
			}else{
				//找到count的值相等的  不必插入新的节点，但要用头插法把节点插入到所含链表的头部
				SimpleNode first=p.getFirst();
				SimpleNode sn=new SimpleNode(node.getData());
				sn.setNext(first);
				//设置头指针
				p.setFirst(sn);
				break;
			}
		}
	}
}
/**
 * 中序遍历 递归算法 p为当前节点的指针
 */
public void middleOrder(TreeNode p){
	if(p!=null){
		//遍历左子树
		this.middleOrder(p.getLeftCh());
		//遍历本次节点的同时，插入到“以出现次数为关键字的二叉排序树”
		this.insertCountNode(p);
		//遍历右子树
		this.middleOrder(p.getRightCh());
	}
}
/**
 * 中序遍历 递归算法 输出
 */
public void middleOrderCountTree(CountNode p){
	if(p!=null){
		//遍历左子树
		this.middleOrderCountTree(p.getLeftCh());
		//遍历本次节点 即遍历整个链表
		SimpleNode sp=p.getFirst();
		System.out.println("出现次数为"+p.getCount()+"的数字有：");
		while(sp!=null){
			System.out.print("   "+sp.getData());
			sp=sp.getNext();
		}
		System.out.println();
		//遍历右子树
		this.middleOrderCountTree(p.getRightCh());
	}
}
/**
 * 插入单个节点的方法
 */
public void insertNode(int data){
	//如果没有根节点 创造新的根节点
	if(this.getRoot()==null){
		root=new TreeNode(data);
	}else{
		//初始化指针p指向根节点
		TreeNode p=root;
		while(true){
			//如果p的data小于data  
			if(p.getData()<data){
				//如果p没有左子树  则直接插入到p的左子树
				if(p.getLeftCh()==null){
					TreeNode leftCh=new TreeNode(data);
					p.setLeftCh(leftCh);
					break;
				}else{
					//如果p有左子树 则让指针指向p的左子树 继续遍历
					p=p.getLeftCh();
					continue;
				}
			}
			//插入右子树的情况 和左子树类似
			else if(p.getData()>data){
				if(p.getRightCh()==null){
					TreeNode rightCh=new TreeNode(data);
					p.setRightCh(rightCh);
					break;
				}else{
					p=p.getRightCh();
					continue;
				}
			}else{
				//设置重复的情况  不必插入新的节点，直接让p的count加1
				int count=p.getCount();
				count++;
				p.setCount(count);
				break;
			}
		}
	}
}

/**
 * 用于测试的类  为了程序的健壮性，我们多生成些随机数放入数组
 */
@Test
public void test(){
	TreeInsert ti=new TreeInsert();
	int[] array={2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
            3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
            7, 8, 8, 7, 8, 7, 9, 0 };
	ti.createTreeAndOutPut(array);
}
}

#33

我觉得试题考的就是一楼的那种思想，重点不是你如何写一个树或者什么，重点是要懂得根据数据的特色来设计相应的算法和结构。就像1楼说了，在这种数字很小的情况下，用数组是最好的方式。用二叉树只能说更具有普遍性，正常人应该都能想到，可是，一楼的方式才更考验了一个人的观察以及处理能力。

#34

引用 31 楼 SmallYamateh 的回复:

第二次的二叉排序的节点：
package tm.cao.sort;

/**
 * 以“出现次数”为关键字的节点  本身包含一个链表  插入的方法为头插法
 *
 */
public class CountNode {

/**
 * 出现次数
 */
private int count;

/**
 * 链表的表头节点
 */
private SimpleNod……

好吧，菜鸟表示 很碉堡，虽然看不懂！

#35

这个可以用映射的Map(Key,Value)的思想。

#36

晕，直接用map就可以了

#37

重点关注解法。

#38

数值分布有限的话，一楼就是好方法。这种箱排序在有限的访问内排序是无敌的，因为比较类排序复杂度都是超过o(NlogN)的，当然代价是对应数组值范围的空间。

未知范围因为要统计每个数字出现次数，用hash和二叉排序树都可以，原因都是快速查找之前是否出现过这个数字。然后遍历hashTable和二叉排序树另外开辟生成数组再进行排序，居然还有人说先平衡二叉树，知道红黑树或者AA树有多少代码多少if-else么。。附个红黑树的代码吧，不过是c++的。。面向对象就更扯不上了。这么复杂笔试调试出来不是扯谈么。

其实数据量小的时候算法都是浮云，20个数，nlogn的快排也许还没n^2冒泡快。

#ifndef RBTREE_H_
#define RBTREE_H_

#include <iostream>
#include <string>
using namespace std;

template<class K,class V>
class RBTree{

private:
	RBTree(const RBTree& input){throw "拷贝构造还没写";}
	const RBTree& operator=(const RBTree& input){throw "=还没写";}
private:
	enum Color{RED,BLACK};

	//直接用外部类的泛型，如果class是public如何保证泛型具体化的？
	class RBNode
	{
	public:
		Color color;
		RBNode *right;
		RBNode *left;
		//对二叉树来回遍历必须需要parent指针，
		//这个和huffman编码类似,本质是二叉双向链表
		RBNode *parent;  
		K key;
		V value;

		RBNode()
		{
			right = 0;
            left = 0;
			parent = 0;
		    
		}

		//修改：多加了一个构造函数
		RBNode(RBNode *left,RBNode *right,RBNode *parent,K key,V value,Color color=RED)
		{
			this->color = color;
			this->key = key;
			this->value = value;
			this->left = left;
			this->right = right;
			this->parent = parent;
		}
	};
private:
	RBNode *nullNode;//很多空节点，都用一个表示
					//省略多余的空判断
	RBNode *root; //二叉树么，肯定有个根
public:
	RBTree()
	{
		this->nullNode = new RBNode();
		this->nullNode->color = BLACK; //空节点肯定是黑色的

		this->root = nullNode;     //根、左右父亲都是空的
		this->nullNode->left = nullNode;
		this->nullNode->right = nullNode;
		this->nullNode->parent = nullNode;

	}



	bool isEmpty()
	{
		if(this->root==this->nullNode)
			return true;
		return false;
	}

	//key必须要重载<运算符，这个std如何保证???
	//如果没有重载，结果是什么？
	RBNode* find(K &key) const//修改：传入引用更效率
	{
		RBNode* iterator = this->root;
		while(iterator!=nullNode)
		{
			if(key<iterator->key)
				iterator = iterator->left;
			else if(key>iterator->key)
				iterator = iterator->right;
			else 
				return iterator;
		}

		return NULL; 
	}

	bool insert(K key,V value)
	{
		//RBNode *insertPoint = this->nullNode;
		RBNode *iterator = this->root;
		RBNode *insertPoint = 0;
		bool flag = false; //是否有这个键的标识
		while(iterator!=nullNode)
		{
			insertPoint = iterator;
			if(key<iterator->key)
				iterator = iterator->left;
			else if(key>iterator->key)
				iterator = iterator->right;
			else{
				flag = true; //修改:已经有这个key就赋新值
				break;
			} 	
		}
		if(flag){//修改：已经有key
			insertPoint->value = value;
		}else{
			//构造默认红色,空树的时候iterator就是root，root->parent还是nullNode
			RBNode *newNode = new RBNode(nullNode,nullNode,iterator->parent,key,value);
			if(root==nullNode){//特例：如果树是空树
				this->root = newNode;

				//nullNode->parent = root;这3句话有必要？
				//nullNode->left = root; 
				//nullNode->right = root;

			}else{//区分要插入在左子树还是右子树
				if(key<insertPoint->key)
					insertPoint->left = newNode;
				else
					insertPoint->right = newNode;
				newNode->parent = insertPoint;
			}
			insertFixUp(newNode);
		}
		return true;

	}

	bool deleteValue(K key)
	{
		RBNode *findNode = this->find(key); //需要被替换的点
		RBNode *deleteNode = 0;//实际删除的点
		RBNode *replacePoint = 0;//颜色校正开始点
		if(findNode==NULL)
			return false;
		if(findNode->left!=nullNode&&findNode->right!=nullNode)//左右子树都存在
		{
			deleteNode = findMin(findNode->right); //找到右子树的最小值
			findNode->value = deleteNode->value;
			findNode->key = deleteNode->key;
			if(deleteNode->parent==findNode)//右孩子就是右子树的最小值
			{
				findNode->right = deleteNode->right;
			}else //没有左孩子，则父亲的左孩子连接删除节点的右孩子
				deleteNode->parent->left = deleteNode->right;
			deleteNode->right->parent = deleteNode->parent;//空节点也要连，方便校正颜色
			replacePoint = deleteNode->right;
		}else{ //直接删除节点，不需要替换值
				/*
					一个孩子为空，删除的可能是根
					而且最多有一个红的孩子

					思路不清楚，写的反而复杂了
				*/
			if(findNode->right==nullNode){

				if(findNode==root)//是根直接更新就好
				{
					root = findNode->left;
					deleteNode = findNode;
					replacePoint = root;
				}else{//不是根需要挂链
					if(findNode->parent->left==findNode)//findNode在父亲的左孩子上
					{
						findNode->parent->left = findNode->left;

					}else{
						findNode->parent->right = findNode->left;
					}
					findNode->left->parent = findNode->parent;
					deleteNode = findNode;
					replacePoint = findNode->left;

				}
			}else if(findNode->right!=nullNode){//右边不是空的
				if(findNode==root)
				{
					root = findNode->right;
					deleteNode = findNode;
					replacePoint = root;
				}else{
					if(findNode->parent->left==findNode)//findNode在父亲的左孩子上
					{
						findNode->parent->left = findNode->right;

					}else{
						findNode->parent->right = findNode->right;
					}
					findNode->right->parent = findNode->parent;
					deleteNode = findNode;
					replacePoint = findNode->right;
				}
			}

		}


		if(deleteNode->color==BLACK) //删除的是黑色的，需要修正
			deleteFixUp(replacePoint);
		delete deleteNode;
		return true;

	}
	void clear()
	{
		clear(root);
	}

	void printTree()
	{
		printTree(root);
		cout<<endl;
	}

	~RBTree()
	{
		clear();
		delete nullNode;
	}

private:
	void insertFixUp(RBNode *node)
	{
		//插入的时候唯一有问题的就是红色节点孩子还是红色
		while(node->parent->color==RED)
		{
			if(node->parent->parent->left==node->parent)//父亲在祖父的左子树上
			{
				RBNode *uncle = node->parent->parent->right;
				if(uncle->color==RED) //叔叔也是红色
				{
					/**
	                     父亲和叔叔都改成黑色，祖父改成红色
						 当前节点变为祖父节点
					*/
					node->parent->color = BLACK;
					uncle->color = BLACK;
					node->parent->parent->color = RED;
					node = node->parent->parent;
				}else{//叔叔黑色
					if(node->parent->right==node)//在父亲的右子树上
					{
						/*
							左旋并且当前节点变成原来的父节点
						*/
						node = node->parent;
						leftRotate(node);
					}else{//在父亲左子树上
						node->parent->color = BLACK;
						node->parent->parent->color = RED;
						rightRotate(node->parent->parent);
					}

				}
			}else{//父亲在祖父的右子树上
				RBNode *uncle = node->parent->parent->left;
				if(uncle->color==RED)
				{
					/*
						父亲和叔叔都是红色的，就全部涂黑，祖父涂红
						当前节点变为祖父
					*/	
					uncle->color = BLACK;
					node->parent->color = BLACK;
					uncle->parent->color = RED;
					node = node->parent->parent;
				}else{//叔叔是黑色的
					if(node->parent->left==node)//当前是父亲的左子树
					{
						/*
							右旋并且当前节点变为原来的父亲节点
							目的是变成父亲的右子树
						*/
						node = node->parent;
						rightRotate(node);

					}else{//当前是父亲的右子树
						/*
							父亲涂黑，祖父涂红，祖父左旋
						*/
						node->parent->color = BLACK;
						node->parent->parent->color = RED;
						leftRotate(node->parent->parent);
					}
				}
			}

		}
		//往上可能已经到了根，直接涂黑就可
		this->root->color = BLACK;
	}

	void leftRotate(RBNode *node)
	{
		/*私有函数，这个判断完全是多余的
		if(node==nullNode||node->right==nullNode)
			return false;
		*/
		RBNode *rightChild = node->right; //存下右孩子

		//处理和node父亲的关系
		if(node==root)//node是根，那么node没有父亲
		{
			root = rightChild;

			/*这2句话有必要么。为什么空节点的左右一定要是根？？
			nullNode->left = root;
			nullNode->right = root;
			*/
		}else{ //
			if(node==node->parent->left)//node是左孩子
			{
				node->parent->left = rightChild;
			}else{
				node->parent->right = rightChild;
			}
			rightChild->parent = node->parent;
		}
		//处理node节点的链
		node->right = rightChild->left;
		rightChild->left->parent = node;

		//处理rightChild，和新父亲已经做完了
		rightChild->left = node;
		node->parent = rightChild;

	}

	void rightRotate(RBNode *node)
	{
		RBNode *leftChild = node->left;

		//处理和父亲的关系
		if(node==root)  //没有父亲
		{
			root = leftChild;
		}else{
			if(node->parent->left==node)
			{
				node->parent->left = leftChild;
			}else{
				node->parent->right = leftChild;
			}
			leftChild->parent = node->parent;
		}

		//处理node
		node->left = leftChild->right;
		leftChild->right->parent = node;

		//处理leftChild,leftChild的父亲已经处理完
		leftChild->right = node;
		node->parent = leftChild;
	}

	RBNode* findMin(RBNode *node)
	{
		while(node!=nullNode&&node->left!=nullNode)
			node = node->left;
		return node;
	}
	void deleteFixUp(RBNode *node)
	{
		while(node->color==BLACK&&node!=root)//删除的是黑色上来的还是黑色就有问题
		{									//根要单独考虑

			if(node->parent->left==node) //当前在父亲的左子树上
			{
				RBNode *bro = node->parent->right;
				if(bro->color==RED)   //兄弟是红色的
				{
					/*
						兄弟涂黑，父亲涂红，左旋
					*/
					bro->color = BLACK;
					node->parent->color = RED;
					leftRotate(node->parent);

				}else{ //兄弟是黑色的
					if(bro->left->color==BLACK && bro->right->color==BLACK)//兄弟左右孩子都是黑色的
					{
						/*
							兄弟涂红，当前节点变成父亲节点
						*/
						bro->color = RED;
						node = node->parent;
					}else if(bro->right->color==BLACK){ //右孩子黑色
						/*
							兄弟涂红，右孩子涂黑,兄弟右旋
						*/
						bro->color = RED;
						bro->left->color = BLACK;
						rightRotate(bro);

					}else{//右孩子是红色
						bro->color = bro->parent->color;
						bro->parent->color = RED;
						bro->right->color =RED;
						leftRotate(bro->parent);
						break;
					}

				}
			}else{ //当前在父亲的右孩子上
				RBNode *bro = node->parent->left;
				if(bro->color==RED)//兄弟红色
				{
					/*
						兄弟涂黑，父亲涂红，父亲右旋
					*/
					bro->color = BLACK;
					node->parent->color = RED;
					rightRotate(bro->parent);
				}else{//兄弟也是黑色的
					if(bro->left->color==BLACK && bro->right->color==BLACK)
					{
						bro->color = RED;
						node = node->parent;
					}else if(bro->left->color==BLACK)//左黑右红
					{
						/*
							右孩子是红色的
							右孩子涂黑，父亲涂红，父亲左旋
							得到左孩子是红色的
						*/

						bro->right->color = BLACK;
						bro->parent->color = RED;
						leftRotate(bro->parent);
					}else{//左孩子是红色的
						bro->color = bro->parent->color;
						bro->left->color = BLACK;
						bro->parent->color = BLACK;
						rightRotate(bro->parent);
						break;
					}

				}

			}

		}

		if(node->color==RED)
		{
			node->color = BLACK;

		}

	}
	void clear(RBNode *node)
	{
		if(node==nullNode)
			return;
		clear(node->left);
		clear(node->right);
		delete node;
	}

	void printTree(RBNode *node)
	{
		if(node==nullNode)
			return;
		printTree(node->left);
		cout<< node->key<<" ";
		printTree(node->right);
	}

};


#endif

#39

引用 38 楼 mingzidaodiduochang 的回复:

数值分布有限的话，一楼就是好方法。这种箱排序在有限的访问内排序是无敌的，因为比较类排序复杂度都是超过o(NlogN)的，当然代价是对应数组值范围的空间。

未知范围因为要统计每个数字出现次数，用hash和二叉排序树都可以，原因都是快速查找之前是否出现过这个数字。然后遍历hashTable和二叉排序树另外开辟生成数组再进行排序，居然还有人说先平衡二叉树，知道红黑树或者A……

领略一下C++牛人的风采。

#40

引用 3 楼 SmallYamateh 的回复:

改变你的数据存储方式，不要仅仅局限于for循环、冒泡之类的线性算法，并且把“面向”对象的思想融入编程。
以下方法，算法的平均复杂度为O(Nlog2N)。
中心思想：遍历数组，依次插入到二叉排序树，如果找到数字相等的，节点的count++；中序遍历算法，输出这个二叉排序树。（PS：如果想得到标准的O(Nlog2N)算法，可以通过旋转树枝的办法，减小树的高度，把二叉排序树……

  碉堡了 数据结构忘得差不多了  

#41

用TreeMap就可以快速实现

/*
	 * 题目：数组中有重复数据，求出每个数据出现的次数并按照次数的由大到小排列出来
	 */
	public static void sortByCount(int[] arr){
		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		for (int i : arr) {
			if(map.containsKey(i)) map.put(i, map.get(i) + 1);
			else map.put(i, 1);
		}
		TreeMap<Integer, String> resultMap = new TreeMap<Integer, String>();
		for (int i : map.keySet()) {
			int key = map.get(i);
			if(resultMap.containsKey(key)) resultMap.put(key, String.format("%s,%d", resultMap.get(key),i));
			else resultMap.put(key, String.valueOf(i));			
		}
		//输出
		for (int key : resultMap.descendingKeySet())
			System.out.println(String.format("数字%s出现了%d次", resultMap.get(key),key));		
	}

	public static void main(String[] args) {
		int array[] = { 12, 5, 16, 22, 14, 13, 15, 14, -22, 5, 2, 4, 12, 6, 13,
				25, 417, 12, -3, -5, 6, -5, 2, 4, 32, 25, 2, 23, 15, 2, -3, 54, 32,
				3, 53, 32, 3, 15, 23, 7, 8, 228, 7, 8, 27, 19, 0, 99 };
		Project1206.sortByCount(array);
	}

结果：
数字2出现了4次
数字12,15,32出现了3次
数字-5,-3,3,4,5,6,7,8,13,14,23,25出现了2次
数字-22,0,16,19,22,27,53,54,99,228,417出现了1次

#42

如果输出时对数字没有排序要求的话，第一个TreeMap可以改成HashMap

#43

想过把这个数查到数据库中 group by 一下 sum() 一下 order by 一下没

#44

import java.util.HashMap;
import java.util.Map;



public class Test {

public static void main(String[] args) {
  int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
                3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
                7, 8, 8, 7, 8, 7, 9, 0 };
  Map map = new HashMap();
  for (int i=0;i<array.length;i++){
  if(map.get(array[i])==null){
  map.put(array[i], 0);
  }
 map.put(array[i], (Integer)map.get(array[i])+1);
  }
  System.out.println(map);
}

}

我这个更简单点

#45

44楼貌似没排序吧？只把每个数出现次数输出了。

#46

#47

引用 23 楼 ku2ran 的回复:

int array[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2,
3, 5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,
7, 8, 8, 7, 8, 7, 9, 0 };
Arrays.sort(array); // 小到……

这个没排序啊

#48

引用 43 楼 joseph_mok 的回复:

想过把这个数查到数据库中 group by 一下 sum() 一下 order by 一下没

这个想法真"牛..."，不过确实是个办法

#49

引用 41 楼 zyc13701469860 的回复:

用TreeMap就可以快速实现
Java code?1234567891011121314151617181920212223242526/*     * 题目：数组中有重复数据，求出每个数据出现的次数并按照次数的由大到小排列出来     */    public static void sortByCount(int[] arr){        TreeMap<In……

学习了

#50

import java.util.Arrays;
import java.util.Comparator;

public class test {
	public static void main(String[] args) {
		int data[] = { 2, 5, 6, 2, 4, 3, 5, 4, 2, 5, 2, 4, 2, 6, 3, 5, 4, 2, 3,
				5, 6, 5, 2, 4, 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 7,
				8, 8, 7, 8, 7, 9, 0 };
		numObj[] tmp = new numObj[10];
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = new numObj(i, 0);
		}
		for (int i = 0; i < data.length; i++) {
			tmp[data[i]].value++;
		}
		Arrays.sort(tmp, new numObj());
		int index = 0;
		for (int i = 0; i < 10; i++) {
			for (int k = 0; k < tmp[i].value; k++) {
				data[index++] = tmp[i].key;
			}
		}
	}
}

class numObj implements Comparator<numObj> {
	int value;
	int key;

	public numObj(int key, int value) {
		super();
		this.value = value;
		this.key = key;
	}

	public numObj() {
		super();
		// TODO Auto-generated constructor stub
	}

	public String toString() {
		return String.valueOf(this.value);
	}

	public int compare(numObj o1, numObj o2) {
		if (o1.value == o2.value)
			return 0;
		else if (o1.value < o2.value) {
			return -1;
		} else
			return 1;
	}

}

见枚举范围有限就搞了个这个，用不着树结构。

那个sort方法随便用别的什么替代也可以，貌似时间效率不咋地。唉～