数据结构与算法--第一个只出现一次的字符

不念不忘少年蓝@ 2022-10-06 00:46 152阅读 0赞

#### 第一个只出现一次的字符 ####

*  题目：在字符串中找出第一个只出现一次的字符，比如输入“wersdfxvsdfwer”，则输出x。
 *  方法一：
    
     *  还是老规矩，初始想法是从头遍历每一个字符，每遍历一个字符都与后面n-1个字符比较
     *  如果发现后面字符中包含相同字符则查询下一个字符
     *  如果后面字符都没有相同的字符，则放回当前字符
     *  方法的时间复杂度是O(n2)
 *  方法一是最简单的方式，时间复杂度最大。接下来开始优化改这个算法
 *  方法二：
    
     *  与次数相关，我们可以将每个字符与出现的次数存储起来，需求开辟额外的存储空间
     *  显然key，value形式的存储第一个想到的是java中的Map结构
     *  通过Map,我们可以通过字符串key，来找到他对应的次数value
     *  有如下实现：

/** * 找出数组中第一个只出现一次的字符 HashMap * @author liaojiamin * @Date:Created in 10:22 2021/6/10 */
    public class FindNotRepeatChar { 
    
    public static void main(String[] args) { 
            System.out.println(findNotRepeatCharHashMap("wersdfxvsdfwer"));
    }
    
    /** * HashMap情况 * */
         public static char findNotRepeatCharHashMap(String str){ 
            if(str == null){ 
                return '\u0000';
            }
            if(str.length() == 1){ 
                return str.charAt(0);
            }
            Map<Character, Integer> map = new HashMap<>();
            char[] target = str.toCharArray();
            for (int i = 0; i < target.length; i++) { 
                Character key = target[i];
                if(map.containsKey(key)){ 
                    map.put(key, map.get(key) + 1);
                }else { 
                    map.put(key, 1);
                }
            }
            for (int i = 0; i < target.length; i++) { 
                if(map.get(target[i]) == 1){ 
                    return target[i];
                }
            }
            return '\u0000';
        }
    
    }

*  如上算法的实现是没问题的，得到的第一个是x，但是此时我们是借助了java的HashMap的api来实现我们的算法
 *  如果只能用基础数据结构以及自己实现的方法呢（如此变态的要求），我们接着来优化。
 *  方法三：
    
     *  在方法二的基础上我们其实只需要解决HashMap存在的顺序问题，能否自定义一个哈希表
     *  因为题目的特殊性，我们需要将先出现的字符放在某个数据结构的前面
     *  那么自定义一个哈希表，直接通过hashCode来指定对应的位置
     *  因为字符char，在C++中是1个字节，8位 28 = 256,在java中是2个字节，16位，65535
     *  那么我们创建一个长度为65535的数组，每个字母根据其ASCII码作为数组下标对应的一个数字，二数组中存储的是每个字符出现的次数
     *  这样我们创建了一个大小为65535，以字符ASCII码作为键值的哈希表
     *  还有一个小的关键点在于，字符的ASCII编码可以直接通过Integer.valueOf得到，恰好，Character的HashCode方法也是直接转int，他是是相等的
     *  如上代码有如下实现：

/** * 找出数组中第一个只出现一次的字符 * @author liaojiamin * @Date:Created in 10:22 2021/6/10 */
    public class FindNotRepeatChar { 
        public static void main(String[] args) { 
            System.out.println(findNotRepeatChar("wersdfxvsdfwer"));
        }
    	
    	/** * 自定义Hash表方法 * */
        public static char findNotRepeatChar(String str){ 
            if(str == null){ 
                return '\u0000';
            }
            if(str.length() == 1){ 
                return str.charAt(0);
            }
    
            int[] charValue = new int[256];
            char[] target = str.toCharArray();
            for (int i = 0; i < target.length; i++) { 
                Integer position = new Character(target[i]).hashCode();
                charValue[position] += 1;
            }
            for (int i = 0; i < target.length; i++) { 
                Integer position = new Character(target[i]).hashCode();
                if(charValue[position] == 1){ 
                    return target[i];
                }
            }
            return '\u0000';
        }
    }

*  以上代码能正确得到我们需要的结果，并且第一次遍历，在哈希表中更新一个字符出现的次数时间是O(1)。如果字符串长度为n，那么一次扫描时间复杂度是O(n)
 *  第二次遍历得到的Hash表同样可以O(1)时间复杂度得到一个字符的次数，所以时间复杂度依然是O(1)
 *  这样总的来说时间复杂度还是O(1)
 *  同时我们需要一个 65535 的整数数组，由于数组的大小是个常数，也就是数组大小不会和目标字符串的长度相关，那么空间复杂度是O(1)
 *  问题：
    
     *  在方法三种，的确可以在纯英文字符的情况下得到确定值，算法也是正确的，但是实际上工作中字符远比65535个多，而且hashCode也会有冲突的时候，比如\*\*\*存在中英文混合情况，方法二就无法求解\*\*\*
 *  方法四：
    
     *  基于方法二的基础上我们解决中英文混用造成的冲突以及顺序问题
     *  我想到了HashMap中用到的哈希冲突解决方法，分离链表发
     *  我们定义一个链表数组，每次冲突后，将冲突元素添加到链表尾部
     *  然后依次遍历找出为 1 的节点即可
     *  如下实现：

/** * 找出数组中第一个只出现一次的字符 * @author liaojiamin * @Date:Created in 10:22 2021/6/10 */
    public class FindNotRepeatChar { 
        public static void main(String[] args) { 
            System.out.println(findNotRepeatCharCompatibleChina("wersdfxxv我sdfwer"));
        }
    /** * 异常情况：无法保证中文，英文数据在数组中顺序 * 包含中文情况 * */
        public static char findNotRepeatCharCompatibleChina(String str){ 
            if(str == null){ 
                return '\u0000';
            }
            if(str.length() == 1){ 
                return str.charAt(0);
            }
            ListNode listArray[] = new ListNode[str.length()];
            char[] target = str.toCharArray();
            for (int i = 0; i < target.length; i++) { 
                Integer position = (new Character(target[i]).hashCode())%str.length();
                if(listArray[position] == null){ 
                    listArray[position] = new ListNode(String.valueOf(target[i]), 1);
                }else { 
                    ListNode listNode = MyLinkedList.search(listArray[position], String.valueOf(target[i]));
                    if(listNode != null){ 
                        listNode.setValue(listNode.getValue()+1);
                    }else { 
                        MyLinkedList.addToTail(listArray[position], String.valueOf(target[i]), 1);
                    }
                }
            }
            for (int i = 0; i < listArray.length; i++) { 
                if(listArray[i] != null){ 
                    ListNode header = listArray[i];
                    while (header != null){ 
                        if(header.getValue() == 1){ 
                            return header.getKey().charAt(0);
                        }
                        header = header.getNext();
                    }
                }
            }
            return '\u0000';
        }
     }

*  如上，算法参照HashMap的思想对hash表进行处理，算法能得到正确的值。
 *  我们试图通过一个 字符串大小的链表数组来存储对应存量数据，其中涉及到HashCode%str.length取模得到对应位置
 *  虽然获取数组位置的时候回有冲突，并且不能保证顺序，但是我们每次都通过原始数组去查找遍历，依然可以得到第一个出现一次的字符
 *  方法中用的链表ListNode，以及链表对应的方法 MyLinkedList 都是自定义的方法，可以在之前的文章：[数据结构与算法–链表实现以及应用][Link 1] 找到详细的实现以及说明。
 *  方法的时间时间复杂度两次遍历都是O(n)
 *  在每次遍历有hash冲突的节点时候，我们需要调用 MyLinkedList.search 找到当前key值对应的节点，此处复杂度取决于hash冲突的多少
 *  因此时间复杂度应该大于O(n)
 *  空间复杂度额外存储于字符串长度正相关也是O(n)
 *  方法五
    
     *  在方法四中算法是正确，但是有一定的复杂度，涉及到hash冲突解决，取模定位，链表节点查询这种复杂的操作
     *  因为我们收到方法三的定式思维影响用的hash表的结构存储，其实完全不用
     *  我们可以用链表存储，不用hash作为key，直接用对应的字符作为key，这样可以用少于O(n)的空间来存储
     *  如上分析有如下实现：

/** * 找出数组中第一个只出现一次的字符 * @author liaojiamin * @Date:Created in 10:22 2021/6/10 */
    public class FindNotRepeatChar { 
        public static void main(String[] args) { 
            System.out.println(findNotRepeatCharCompatibleChinaLinkList("哈哈wersvdfxx我v我sdfwer去"));
        }
     /** * 用链表解决 * */
        public static char findNotRepeatCharCompatibleChinaLinkList(String str) { 
            if (str == null) { 
                return '\u0000';
            }
            if (str.length() == 1) { 
                return str.charAt(0);
            }
            //初始化链表
            ListNode listNode  = new ListNode(String.valueOf(str.charAt(0)), 1);
            char[] target = str.toCharArray();
            for (int i = 1; i < target.length; i++) { 
                ListNode header = MyLinkedList.search(listNode, String.valueOf(target[i]));
                if(header != null){ 
                    header.setValue(header.getValue() + 1);
                }else { 
                    MyLinkedList.addToTail(listNode, String.valueOf(target[i]), 1);
                }
            }
            for (int i = 0; i < target.length; i++) { 
                ListNode targetNode = MyLinkedList.search(listNode, String.valueOf(target[i]));
                if(targetNode != null && targetNode.getValue() == 1){ 
                    return target[i];
                }
    
            }
            return '\u0000';
        }
    }

*  如上用链表存储的实现方式时间复杂度与之前一样，也是大于O(n)，但是在代码复杂度上减少很多
 *  此方法不涉及到hash冲突解决等问题，都是直接存储，空间复杂度是小于O(n)的

[上一篇：数据结构与算法–丑数][Link 2]  
[下一篇：数据结构与算法–数组中的逆序对][Link 3]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/114397878
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/117743362
[Link 3]: https://blog.csdn.net/liaojiamin0102/article/details/117823999