我是用 二维数组做的,有没有更好的答案
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]]++;
}
所以统计过程可以简化为只需要一个 一维数组来完成:
int[] count = new int[10];
for (int i = 0;i<array.length;i++) {
count[array[i]]++;
}
#2
谢谢,学习了
#3
改变你的数据存储方式,不要仅仅局限于for循环、冒泡之类的线性算法,并且把“面向”对象的思想融入编程。
以下方法,算法的平均复杂度为O(Nlog2N)。
中心思想:遍历数组,依次插入到二叉排序树,如果找到数字相等的,节点的count++;中序遍历算法,输出这个二叉排序树。(PS:如果想得到标准的O(Nlog2N)算法,可以通过旋转树枝的办法,减小树的高度,把二叉排序树优化为平衡二叉树。)
节点类:
二叉排序树的类:
以下方法,算法的平均复杂度为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
数字=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
碉堡了
#6
受教了。
#7
#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
数据结构完全忘了,你太吊了
#11
#12
3楼的MM厉害啊,不但算法熟,面向对象的精髓也理解的透,佩服,佩服!
#13
请问 #9 的方法 如何解决排序问题?
#14
9楼的HashMap换成TreeMap就行了
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());
}
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
这个排序有点麻烦吧
#18
谢谢,又学到了点知识
#19
能想到集合框架固然好,但是,某些时候的笔试和面试,是禁用Java集合框架的。
#20
是啊,面试的时候不让使用 api 里现成的方法
#21
呵呵,这也和面试官有关,有的面试官考察思维,有的注重考察对API的熟悉情况,反正我感觉两方面都要练习。
#22
想了半天也没想明白,是怎么一次遍历直接生成的二叉树。
仔细一看。。。
原来是按数的大小排序出来的,不是数字出现的次数。
竟然没人吐糟。都被这可爱的头像迷倒了吧。
#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));
}
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
好吧,你等等,哈;确实看错了题目,我再研究研究。
#25
误导大家了哈,等我再考虑考虑,我看错题目了。
#26
#27
学习
#28
对不起大家,哈;结果已经出来了,依然是二叉排序树,等我写上注释。
结果:
出现次数为13的数字有:
2
出现次数为11的数字有:
5
出现次数为7的数字有:
3
出现次数为5的数字有:
4
出现次数为3的数字有:
6 7 8
出现次数为1的数字有:
0 9
结果:
出现次数为13的数字有:
2
出现次数为11的数字有:
5
出现次数为7的数字有:
3
出现次数为5的数字有:
4
出现次数为3的数字有:
6 7 8
出现次数为1的数字有:
0 9
#29
妹子。你真真误导了大家。
这群屌丝。哎。。。
妹子你真是妹子嘛?
哎。。
正解。
楼猪的也挺好的。。。。
#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 + "]";
}
}
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
好吧,菜鸟表示 很碉堡,虽然看不懂!
#35
这个可以用映射的Map(Key,Value)的思想。
#36
晕,直接用map就可以了
#37
重点关注解法。
#38
数值分布有限的话,一楼就是好方法。这种箱排序在有限的访问内排序是无敌的,因为比较类排序复杂度都是超过o(NlogN)的,当然代价是对应数组值范围的空间。
未知范围因为要统计每个数字出现次数,用hash和二叉排序树都可以,原因都是快速查找之前是否出现过这个数字。然后遍历hashTable和二叉排序树另外开辟生成数组再进行排序,居然还有人说先平衡二叉树,知道红黑树或者AA树有多少代码多少if-else么。。附个红黑树的代码吧,不过是c++的。。面向对象就更扯不上了。这么复杂笔试调试出来不是扯谈么。
其实数据量小的时候算法都是浮云,20个数,nlogn的快排也许还没n^2冒泡快。
未知范围因为要统计每个数字出现次数,用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
领略一下C++牛人的风采。
#40
碉堡了 数据结构忘得差不多了
#41
用TreeMap就可以快速实现
结果:
数字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次
/*
* 题目:数组中有重复数据,求出每个数据出现的次数并按照次数的由大到小排列出来
*/
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);
}
}
我这个更简单点
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
这个没排序啊
#48
这个想法真"牛...",不过确实是个办法
#49
学习了
#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方法随便用别的什么替代也可以,貌似时间效率不咋地。唉~
#1
数字都很小,最小到最大只不过是 0~9
所以统计过程可以简化为只需要一个 一维数组来完成:
int[] count = new int[10];
for (int i = 0;i<array.length;i++) {
count[array[i]]++;
}
所以统计过程可以简化为只需要一个 一维数组来完成:
int[] count = new int[10];
for (int i = 0;i<array.length;i++) {
count[array[i]]++;
}
#2
谢谢,学习了
#3
改变你的数据存储方式,不要仅仅局限于for循环、冒泡之类的线性算法,并且把“面向”对象的思想融入编程。
以下方法,算法的平均复杂度为O(Nlog2N)。
中心思想:遍历数组,依次插入到二叉排序树,如果找到数字相等的,节点的count++;中序遍历算法,输出这个二叉排序树。(PS:如果想得到标准的O(Nlog2N)算法,可以通过旋转树枝的办法,减小树的高度,把二叉排序树优化为平衡二叉树。)
节点类:
二叉排序树的类:
以下方法,算法的平均复杂度为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
数字=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
碉堡了
#6
受教了。
#7
#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
数据结构完全忘了,你太吊了
#11
#12
3楼的MM厉害啊,不但算法熟,面向对象的精髓也理解的透,佩服,佩服!
#13
请问 #9 的方法 如何解决排序问题?
#14
9楼的HashMap换成TreeMap就行了
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());
}
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
这个排序有点麻烦吧
#18
谢谢,又学到了点知识
#19
能想到集合框架固然好,但是,某些时候的笔试和面试,是禁用Java集合框架的。
#20
是啊,面试的时候不让使用 api 里现成的方法
#21
呵呵,这也和面试官有关,有的面试官考察思维,有的注重考察对API的熟悉情况,反正我感觉两方面都要练习。
#22
想了半天也没想明白,是怎么一次遍历直接生成的二叉树。
仔细一看。。。
原来是按数的大小排序出来的,不是数字出现的次数。
竟然没人吐糟。都被这可爱的头像迷倒了吧。
#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));
}
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
好吧,你等等,哈;确实看错了题目,我再研究研究。
#25
误导大家了哈,等我再考虑考虑,我看错题目了。
#26
#27
学习
#28
对不起大家,哈;结果已经出来了,依然是二叉排序树,等我写上注释。
结果:
出现次数为13的数字有:
2
出现次数为11的数字有:
5
出现次数为7的数字有:
3
出现次数为5的数字有:
4
出现次数为3的数字有:
6 7 8
出现次数为1的数字有:
0 9
结果:
出现次数为13的数字有:
2
出现次数为11的数字有:
5
出现次数为7的数字有:
3
出现次数为5的数字有:
4
出现次数为3的数字有:
6 7 8
出现次数为1的数字有:
0 9
#29
妹子。你真真误导了大家。
这群屌丝。哎。。。
妹子你真是妹子嘛?
哎。。
正解。
楼猪的也挺好的。。。。
#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 + "]";
}
}
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
好吧,菜鸟表示 很碉堡,虽然看不懂!
#35
这个可以用映射的Map(Key,Value)的思想。
#36
晕,直接用map就可以了
#37
重点关注解法。
#38
数值分布有限的话,一楼就是好方法。这种箱排序在有限的访问内排序是无敌的,因为比较类排序复杂度都是超过o(NlogN)的,当然代价是对应数组值范围的空间。
未知范围因为要统计每个数字出现次数,用hash和二叉排序树都可以,原因都是快速查找之前是否出现过这个数字。然后遍历hashTable和二叉排序树另外开辟生成数组再进行排序,居然还有人说先平衡二叉树,知道红黑树或者AA树有多少代码多少if-else么。。附个红黑树的代码吧,不过是c++的。。面向对象就更扯不上了。这么复杂笔试调试出来不是扯谈么。
其实数据量小的时候算法都是浮云,20个数,nlogn的快排也许还没n^2冒泡快。
未知范围因为要统计每个数字出现次数,用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
领略一下C++牛人的风采。
#40
碉堡了 数据结构忘得差不多了
#41
用TreeMap就可以快速实现
结果:
数字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次
/*
* 题目:数组中有重复数据,求出每个数据出现的次数并按照次数的由大到小排列出来
*/
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);
}
}
我这个更简单点
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
这个没排序啊
#48
这个想法真"牛...",不过确实是个办法
#49
学习了
#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方法随便用别的什么替代也可以,貌似时间效率不咋地。唉~