每天一道劍指offer-第一個只出現一次的字元

• 2019 年 10 月 4 日
• 筆記

題目

每天一道劍指offer-第一個只出現一次的字元

https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

題目詳述

在一個字元串(0<=字元串長度<=10000，全部由字母組成)中找到第一個只出現一次的字元,並返回它的位置, 如果沒有則返回 -1（需要區分大小寫）.

思路

• 字元串中的字元都是英文的字母，所以每一個字母都有一個ASCII碼與其對應，然後建立一個字元數組長度是256，可以把每一個字元對應一個數組的下標
• 然後設立一個index！然後比如字元a第一次出現那麼strArray[a字元對應的ASC碼] = index;然後如果下一次a再出現了，那麼strArray[a字元對應的ASC碼] = -1；這樣子做，只要字元出現了大於等於2次，都會這樣子等於-1
• 而只出現一次的字元，由於index這個變數是每次遞增的！我們只需要遍歷一遍，找index最小的那個字元。

題目詳解

public class Solution {      public int FirstNotRepeatingChar(String str) {          if(str.equals(""))              return -1;          int [] temp = new int[256];          int index = 1;          char [] strArray = str.toCharArray();          for(int i=0;i<strArray.length;i++)          {              if(temp[(int)strArray[i]] == 0)              {                  temp[(int)strArray[i]] = index;                  index++;              }else{                  temp[(int)strArray[i]] = -1;              }          }//這個循環就是遍歷一遍，找到出現一次的字元          //只要index大於0就是出現一次的字元          int minIndex = Integer.MAX_VALUE;          char ch = '1';          for(int i=0;i<temp.length;i++)          {              if(temp[i] > 0)              {                  if(temp[i] < minIndex)                  {//找最小的index對應的字元                      minIndex = temp[i];                      ch = (char)i;                  }              }          }          int result = -1;          for(int i=0;i<strArray.length;i++)          {//去找這個字元的下標！              if(strArray[i] == ch)                  return i;          }          return -1;      }  }