给定一个字符类型数组chas[]
判断chas中所有字符是否都只出现过一次
要求:
1.时间复杂度保证为N
2.实现额外空间复杂度为 1,尽量降低时间复杂度
分析:
1),通常排序的做法可以做到时间复杂度为N,只是遍历一遍数组,一般而言,空间复杂度至少为N
2)采用堆排序可以保证额外空间复杂度为1,
什么是堆排序,(涉及大根堆,小根堆)
public void heapSort(char[] chas){
for(int i = 0; i < chas.length; i++){
heapInsert(chas,i);
}
for(int i =chas.length - 1 ;i > 0; i --){
swap(chas,0,i);
heapIsY(chas,0,i);
}
}
//大根堆
public void heapInsert(char[] chars,int i ){
//寻找父亲节点
int parent = 0;
while (i != 0 ){
parent = (i - 1)/2;
if(chars[parent] < chars[i]){
swap(chars,parent,i);
i = parent;
}else {
break;
}
}
}
//大根堆的验证?
public void heapIsY(char[] chas, int i , int size){
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i; //最大值的索引值
while (left < size){
//左边比右边的大,即比左孩子节点大
if(chas[left] > chas[i]){
largest = left;
}
if(right < i && chas[right] > chas[i]){
largest = right;
}
if(largest != i){ //最大值不是父节点
swap(chas,largest,i);
}else {
break;
}
i = largest;
left = i*2 + 1;
left = i*2 + 2;
}
}
public void swap(char[] chars,int i1, int i2){
char tmp = chars[i1];
chars[i1] = chars[i2];
chars[i2] = tmp;
}