2.2 字符串-判断字符数组中字符是否只出现过一次（这道题的堆排序未能啃下，需复习）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2.2 字符串-判断字符数组中字符是否只出现过一次（这道题的堆排序未能啃下，需复习），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1191字，纯文字阅读大概需要2分钟。

内容图文

给定一个字符类型数组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;
    }

内容总结

以上是互联网集市为您收集整理的2.2 字符串-判断字符数组中字符是否只出现过一次（这道题的堆排序未能啃下，需复习）全部内容，希望文章能够帮你解决2.2 字符串-判断字符数组中字符是否只出现过一次（这道题的堆排序未能啃下，需复习）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---