题目:数组中有重复数据,求出每个数据出现的次数并按照次数的由大到小排列出来我是用 二维数组做的,有没有更好的答案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]);
}
}
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]);
}
}
int[] count = new int[10];
for (int i = 0;i<array.length;i++) {
count[array[i]]++;
}
以下方法,算法的平均复杂度为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);
}
}
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;
}
TreeMap是个红黑树吧,我记得。
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());
}
是啊,面试的时候不让使用 api 里现成的方法
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));
}
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 + "]";
}}
*为了计算方便,这是简单的节点类,只包含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);
}
}
#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
* 题目:数组中有重复数据,求出每个数据出现的次数并按照次数的由大到小排列出来
*/
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次
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.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方法随便用别的什么替代也可以,貌似时间效率不咋地。唉~
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); // 小到大顺序 Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer a : array) {
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));
}
}
private static Map<Integer, Integer> hm = new LinkedHashMap<Integer, Integer>(); private static Map<Integer, Integer> tm = new TreeMap<Integer, Integer>(
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 > o2) {
return -1;
}
return 1;
}
}); private static void count(int[] arr) {
for (int num : arr) {
hm.put(num, hm.get(num) == null ? 1 : hm.get(num) + 1);
}
} 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 }; count(array); for (Entry<Integer, Integer> e : hm.entrySet()) {
tm.put(e.getValue(), e.getKey());
} for (Entry<Integer, Integer> e : tm.entrySet()) {
System.out.println(e.getValue() + " : " + e.getKey());
}
}
运行结果是(第一列是元素,第二列是出现的次数):
2 : 13
5 : 11
3 : 7
4 : 5
6 : 3
7 : 3
8 : 3
0 : 1
9 : 1
for(int j = i + 1 ; j < array.length ; j ++){
if(array[i] <= array[j]){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
int count = 1;
for(int i = 0 ; i < array.length ; i++){
int j = i + 1;
if( j < array.length){
if(array[i] == array[i+1]){
count++;
}
if(array[i] != array[i+1]){
System.out.println(array[i]+"--"+count+"次");
count = 1;
}
}else{
System.out.println(array[i]+"--"+count+"次");
}
}
public class TestMap{
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<Integer,Integer> map = new Map<Integer,Integer>();
for(int i=0;i<array.length;i++) {
Integer index = (Integer)map.get(array[i]);
index = index == null ? 0 : index;
map.put(array[i],++index);
}
System.out.println(map);
}
}
package com.yanzhen.test20121213;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;/**
*
* @author walkman
* @date 2012/12/14
* @content 取出重复数据并按出现次数排序
*/
public class DuplicateDataFilter { @SuppressWarnings("unchecked")
public static void main(String[] args) {
int numberArray[] = { 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 length = numberArray.length;
Map<Integer, Integer> numberMap = new HashMap<Integer, Integer>();
for (int i = 0; i < length; i++) {
numberMap.put(numberArray[i],
numberMap.get(numberArray[i]) == null ? 1 : numberMap
.get(numberArray[i]) + 1);
} System.out.println(numberMap); List<Map.Entry<Integer, Integer>> entries = new ArrayList<Map.Entry<Integer, Integer>>(
numberMap.entrySet());
Collections.sort(entries, new Comparator() {
public int compare(Object obj1, Object obj2) {
Object key1 = ((Map.Entry) obj1).getKey();
Object key2 = ((Map.Entry) obj2).getKey(); return ((Comparable) key1).compareTo(key2);
}
}); for(int j = 0; j < entries.size(); j++) {
System.out.print(entries.get(j).toString() + " ");
}
}
}具体的代码贴出来
{
if(array == null || array.length ==0)
{
return new Integer[0];
}
int length = array.length;
Arrays.sort(array);
List<Integer> list2 = Arrays.asList(array);
List<Integer> list3 = new ArrayList<Integer>(length);
for(int i = 0; i < length; i ++)
{
Integer target = list2.get(i);
//起点
int p1 = list2.indexOf(target);
//终点
int p2 = list2.lastIndexOf(target);
list3.add(p2 - p1 + 1);
i = p2;
}
Integer result[] = new Integer[length];
//从小到大排序
Collections.sort(list3);
//从大到小排序
Collections.reverse(list3);
result = list3.toArray(result);
return result;
}
统计完之后就是排序了,和常规的排序没啥区别,最优的也就是NlogN了。快排、归并、或者堆排都可以。
自己做一个数据结构
大概是一个HASH 和一个HEAP(连续数组去实现的极大堆)
HASH 记录 元素在HEAP 中的位置
每个新的数字都直接丢在HEAP 的最后 因为 1 肯定是最小的
其他的数字 通过HASH 去找到对应的位置 +1,接着整理HEAP(递归和父节点比较)最后用堆排的方式 从大到小获取数据速度应该会比二叉排序树快,二叉排序树的每次平衡的时间比较浪费,而且并不适合从中间修改节点的值,从中间修改其实和堆重整类似,但是堆只要和父节点比较,二叉排序树,除了父节点可能还要和右节点比较(左小右大的二叉排序树)。
public static void main(String args[]){
Integer 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 };
List<Integer> linkList = new LinkedList<Integer>();
Collections.addAll(linkList , array);
Map<Integer , Integer> map = new HashMap<Integer , Integer>();
for(Iterator iter = linkList.iterator();iter.hasNext();){
Integer i = (Integer)iter.next();
if(map.containsKey(i)){
map.put(i, map.get(i)+1);
}else{
map.put(i , 1);
}
}
List list = new ArrayList(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(Iterator iter = list.iterator();iter.hasNext();){
Entry<Integer,Integer> e = (Entry<Integer,Integer>)iter.next();
System.out.println(e.getKey() + " , " + e.getValue());
}
}
}