第一個(gè)只出現(xiàn)一次的字符

• 題目：在字符串中找出第一個(gè)只出現(xiàn)一次的字符，比如輸入“wersdfxvsdfwer”，則輸出x。

• 方法一：

  • 還是老規(guī)矩，初始想法是從頭遍歷每一個(gè)字符，每遍歷一個(gè)字符都與后面n-1個(gè)字符比較
  • 如果發(fā)現(xiàn)后面字符中包含相同字符則查詢下一個(gè)字符
  • 如果后面字符都沒有相同的字符，則放回當(dāng)前字符
  • 方法的時(shí)間復(fù)雜度是O(n²)

• 方法一是最簡(jiǎn)單的方式，時(shí)間復(fù)雜度最大。接下來開始優(yōu)化改這個(gè)算法

• 方法二：

  • 與次數(shù)相關(guān)，我們可以將每個(gè)字符與出現(xiàn)的次數(shù)存儲(chǔ)起來，需求開辟額外的存儲(chǔ)空間
  • 顯然key，value形式的存儲(chǔ)第一個(gè)想到的是java中的Map結(jié)構(gòu)
  • 通過Map,我們可以通過字符串key，來找到他對(duì)應(yīng)的次數(shù)value
  • 有如下實(shí)現(xiàn)：

/*** 找出數(shù)組中第一個(gè)只出現(xiàn)一次的字符 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';}}

• 如上算法的實(shí)現(xiàn)是沒問題的，得到的第一個(gè)是x，但是此時(shí)我們是借助了java的HashMap的api來實(shí)現(xiàn)我們的算法

• 如果只能用基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)以及自己實(shí)現(xiàn)的方法呢（如此變態(tài)的要求），我們接著來優(yōu)化。

• 方法三：

  • 在方法二的基礎(chǔ)上我們其實(shí)只需要解決HashMap存在的順序問題，能否自定義一個(gè)哈希表
  • 因?yàn)轭}目的特殊性，我們需要將先出現(xiàn)的字符放在某個(gè)數(shù)據(jù)結(jié)構(gòu)的前面
  • 那么自定義一個(gè)哈希表，直接通過hashCode來指定對(duì)應(yīng)的位置
  • 因?yàn)樽址鹀har，在C++中是1個(gè)字節(jié)，8位 2⁸ = 256,在java中是2個(gè)字節(jié)，16位，65535
  • 那么我們創(chuàng)建一個(gè)長(zhǎng)度為65535的數(shù)組，每個(gè)字母根據(jù)其ASCII碼作為數(shù)組下標(biāo)對(duì)應(yīng)的一個(gè)數(shù)字，二數(shù)組中存儲(chǔ)的是每個(gè)字符出現(xiàn)的次數(shù)
  • 這樣我們創(chuàng)建了一個(gè)大小為65535，以字符ASCII碼作為鍵值的哈希表
  • 還有一個(gè)小的關(guān)鍵點(diǎn)在于，字符的ASCII編碼可以直接通過Integer.valueOf得到，恰好，Character的HashCode方法也是直接轉(zhuǎn)int，他是是相等的
  • 如上代碼有如下實(shí)現(xiàn)：

/*** 找出數(shù)組中第一個(gè)只出現(xiàn)一次的字符* @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';} }

• 以上代碼能正確得到我們需要的結(jié)果，并且第一次遍歷，在哈希表中更新一個(gè)字符出現(xiàn)的次數(shù)時(shí)間是O(1)。如果字符串長(zhǎng)度為n，那么一次掃描時(shí)間復(fù)雜度是O(n)

• 第二次遍歷得到的Hash表同樣可以O(shè)(1)時(shí)間復(fù)雜度得到一個(gè)字符的次數(shù)，所以時(shí)間復(fù)雜度依然是O(1)

• 這樣總的來說時(shí)間復(fù)雜度還是O(1)

• 同時(shí)我們需要一個(gè) 65535 的整數(shù)數(shù)組，由于數(shù)組的大小是個(gè)常數(shù)，也就是數(shù)組大小不會(huì)和目標(biāo)字符串的長(zhǎng)度相關(guān)，那么空間復(fù)雜度是O(1)

• 問題：

  • 在方法三種，的確可以在純英文字符的情況下得到確定值，算法也是正確的，但是實(shí)際上工作中字符遠(yuǎn)比65535個(gè)多，而且hashCode也會(huì)有沖突的時(shí)候，比如***存在中英文混合情況，方法二就無法求解***

• 方法四：

  • 基于方法二的基礎(chǔ)上我們解決中英文混用造成的沖突以及順序問題
  • 我想到了HashMap中用到的哈希沖突解決方法，分離鏈表發(fā)
  • 我們定義一個(gè)鏈表數(shù)組，每次沖突后，將沖突元素添加到鏈表尾部
  • 然后依次遍歷找出為 1 的節(jié)點(diǎn)即可
  • 如下實(shí)現(xiàn)：

/*** 找出數(shù)組中第一個(gè)只出現(xiàn)一次的字符* @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"));} /*** 異常情況：無法保證中文，英文數(shù)據(jù)在數(shù)組中順序* 包含中文情況* */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的思想對(duì)hash表進(jìn)行處理，算法能得到正確的值。

• 我們?cè)噲D通過一個(gè) 字符串大小的鏈表數(shù)組來存儲(chǔ)對(duì)應(yīng)存量數(shù)據(jù)，其中涉及到HashCode%str.length取模得到對(duì)應(yīng)位置

• 雖然獲取數(shù)組位置的時(shí)候回有沖突，并且不能保證順序，但是我們每次都通過原始數(shù)組去查找遍歷，依然可以得到第一個(gè)出現(xiàn)一次的字符

• 方法中用的鏈表ListNode，以及鏈表對(duì)應(yīng)的方法 MyLinkedList 都是自定義的方法，可以在之前的文章：數(shù)據(jù)結(jié)構(gòu)與算法–鏈表實(shí)現(xiàn)以及應(yīng)用 找到詳細(xì)的實(shí)現(xiàn)以及說明。

• 方法的時(shí)間時(shí)間復(fù)雜度兩次遍歷都是O(n)

• 在每次遍歷有hash沖突的節(jié)點(diǎn)時(shí)候，我們需要調(diào)用 MyLinkedList.search 找到當(dāng)前key值對(duì)應(yīng)的節(jié)點(diǎn)，此處復(fù)雜度取決于hash沖突的多少

• 因此時(shí)間復(fù)雜度應(yīng)該大于O(n)

• 空間復(fù)雜度額外存儲(chǔ)于字符串長(zhǎng)度正相關(guān)也是O(n)

• 方法五

  • 在方法四中算法是正確，但是有一定的復(fù)雜度，涉及到hash沖突解決，取模定位，鏈表節(jié)點(diǎn)查詢這種復(fù)雜的操作
  • 因?yàn)槲覀兪盏椒椒ㄈ亩ㄊ剿季S影響用的hash表的結(jié)構(gòu)存儲(chǔ)，其實(shí)完全不用
  • 我們可以用鏈表存儲(chǔ)，不用hash作為key，直接用對(duì)應(yīng)的字符作為key，這樣可以用少于O(n)的空間來存儲(chǔ)
  • 如上分析有如下實(shí)現(xiàn)：

/*** 找出數(shù)組中第一個(gè)只出現(xià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';} }

• 如上用鏈表存儲(chǔ)的實(shí)現(xiàn)方式時(shí)間復(fù)雜度與之前一樣，也是大于O(n)，但是在代碼復(fù)雜度上減少很多
• 此方法不涉及到hash沖突解決等問題，都是直接存儲(chǔ)，空間復(fù)雜度是小于O(n)的

上一篇：數(shù)據(jù)結(jié)構(gòu)與算法–丑數(shù)
下一篇：數(shù)據(jù)結(jié)構(gòu)與算法–數(shù)組中的逆序?qū)?/p>

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法--第一个只出现一次的字符的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。