<!DOCTYPE html>
<html lang="en">

<head>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta name="description" content="剑指Offer题解（Java实现）">
  <meta name="generator" content="Hugo 0.24.1" />

  <title>第一个只出现一次的字符 &middot; Hov&#39;s Blog</title>

  <script>
	var _hmt = _hmt || [];
	(function() {
	  var hm = document.createElement("script");
	  hm.src = "https://hm.baidu.com/hm.js?dd096f3aba9332e2640cda59d3786695";
	  var s = document.getElementsByTagName("script")[0]; 
	  s.parentNode.insertBefore(hm, s);
	})();
	</script>	
  
  
  
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pure/0.6.2/pure-min.css">

  <!--[if lte IE 8]>
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pure/0.6.2/grids-responsive-old-ie-min.css">
  <![endif]-->
  <!--[if gt IE 8]><!-->
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pure/0.6.2/grids-responsive-min.css">
  <!--<![endif]-->

  <!--[if lte IE 8]>
  <link rel="stylesheet" href="https://HauyuChen.github.io/css/side-menu-old-ie.css">
  <![endif]-->
  <!--[if gt IE 8]><!-->
  <link rel="stylesheet" href="https://HauyuChen.github.io/css/side-menu.css">
  <!--<![endif]-->

  <link rel="stylesheet" href="https://HauyuChen.github.io/css/blackburn.css">

  
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css">

  
  <link href="https://fonts.googleapis.com/css?family=Raleway" rel="stylesheet" type="text/css">

  
  

  
  <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.11.0/styles/androidstudio.min.css">
  <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.11.0/highlight.min.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
  

  <link rel="shortcut icon" href="https://HauyuChen.github.io/img/favicon.ico" type="image/x-icon" />

  
  


</head>


<body>

<div id="layout">

  
<a href="#menu" id="menuLink" class="menu-link">
  
  <span></span>
</a>
<div id="menu">

  <a class="pure-menu-heading brand" href="https://HauyuChen.github.io/">
  <img src="https://HauyuChen.github.io/img/Hov.jpg" width="125px">
</a>

  <div class="pure-menu">
    <ul class="pure-menu-list">
      
      
        <li class="pure-menu-item">
          <a class="pure-menu-link" href="https://HauyuChen.github.io/"><i class='fa fa-home fa-fw'></i>主页</a>
      
        </li>
      
      
        <li class="pure-menu-item">
          <a class="pure-menu-link" href="https://HauyuChen.github.io/post/"><i class='fa fa-list fa-fw'></i>所有文章</a>
      
        </li>
      
      
        <li class="pure-menu-item">
          <a class="pure-menu-link" href="https://HauyuChen.github.io/tags/"><i class='fa fa-folder fa-fw'></i>文章分类</a>
      
        </li>
      
      
        <li class="pure-menu-item">
          <a class="pure-menu-link" href="https://HauyuChen.github.io/topics/"><i class='fa fa-tags fa-fw'></i>关键词</a>
      
        </li>
      
      
        <li class="pure-menu-item">
          <a class="pure-menu-link" href="https://HauyuChen.github.io/booklist/"><i class='fa fa-list fa-fw'></i>技术书单</a>
      
        </li>
      
      
        <li class="pure-menu-item">
          <a class="pure-menu-link" href="https://HauyuChen.github.io/about-me/"><i class='fa fa-user fa-fw'></i>关于我</a>
      
        </li>
      
      
        <li class="pure-menu-item">
          <a class="pure-menu-link" href="https://HauyuChen.github.io/about-site/"><i class='fa fa-home fa-fw'></i>关于本站</a>
      
        </li>
      
    </ul>
  </div>

  <div class="pure-menu social">

  <ul class="pure-menu-list">
    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    
    <li class="pure-menu-item">
      <a class="pure-menu-link" href="https://github.com/HauyuChen" target="_blank"><i class="fa fa-github-square fa-fw"></i>GitHub</a>
    </li>
    

    

    

    

    

    

    

    

    

    

    

    

    
	</ul>
	<ul class="pure-menu-list">
	
	<li class="pure-menu-item">
      <a class="pure-menu-link" href="http://blog.csdn.net/u014134180" target="_blank"><i class="fa fa-lastfm-square fa-fw"></i>友链：Wu_Being</a>
    </li>
  </ul>
  
</div>


  <div>


</div>

</div>


  <div id="main">


<div class="header">
  <h1>第一个只出现一次的字符</h1>
  <h2>剑指Offer题解（Java实现）</h2>
</div>
<div class="content">

  <div class="post-meta">

  <div>
    <i class="fa fa-calendar fa-fw"></i>
    <time>2018-04-01</time>
  </div>

  

  
  
  
  <div>
    <i class="fa fa-folder fa-fw"></i>
    
      <a class="post-taxonomy-tag" href="https://HauyuChen.github.io/tags/%E7%AE%97%E6%B3%95">算法</a>
    
  </div>
  
  

  
  
  
  <div>
	<i class="fa fa-tags fa-fw"></i>
    
      <a class="post-taxonomy-topic" href="https://HauyuChen.github.io/topics/%E7%AE%97%E6%B3%95">算法</a>&nbsp;&#47;
    
      <a class="post-taxonomy-topic" href="https://HauyuChen.github.io/topics/%E5%89%91%E6%8C%87offer">剑指Offer</a>
    
  </div>
  
  
  
</div>

  <p></p>

<hr />

<p><br/></p>

<h1 id="1-题目描述">1 题目描述</h1>

<hr />

<p>在一个字符串(1&lt;=字符串长度&lt;=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。</p>

<p><br/></p>

<h1 id="2-思路">2 思路</h1>

<hr />

<p>本题很容易想到用一个容器暂存字符出现的次数，但是用 HashMap 这样的容器（如解法一）在某些情况下的时间复杂度并不是线性的，因为 HashMap 的 get 方法的时间复杂度取决于冲突个数。</p>

<p>真正的线性时间复杂度的解法可以通过定义一个哈希表来实现（如解法二），用数组存放每个元素的 ASCII 码。</p>

<p><br/></p>

<h1 id="3-代码实现">3 代码实现</h1>

<hr />

<h2 id="解法一">解法一：</h2>

<pre><code>import java.util.HashMap;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str==null){
            return -1;
        }
        
        HashMap&lt;Character,Integer&gt; hm = new HashMap&lt;Character,Integer&gt;();
        
        for(int i=0;i&lt;str.length();i++){
            char ch = str.charAt(i);
            if(!hm.containsKey(ch)){
                hm.put(ch,1);
            }
            else{
                hm.replace(ch,hm.get(ch)+1);
            }
        }
        for(int i=0;i&lt;str.length();i++){
            if(hm.get(str.charAt(i))==1){
                return i;
            }
        }
        return -1;
    }
}
</code></pre>

<h2 id="解法二">解法二：</h2>

<pre><code>public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str==null){
            return -1;
        }
        
        int[] hashTable = new int[256];
        for(int i=0;i&lt;256;i++){
            hashTable[i] = 0;
        }
        for(int i=0;i&lt;str.length();i++){
            hashTable[str.charAt(i)]++;
        }

        for(int i=0;i&lt;str.length();i++){
            if(hashTable[str.charAt(i)]==1){
                return i;
            }
        }
        return -1;
    }
}
</code></pre>

<p><br/></p>

  
<div class="prev-next-post pure-g">
  <div class="pure-u-1-24" style="text-align: left;">
    
    <a href="https://HauyuChen.github.io/post/%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%8E%92%E5%88%97/"><i class="fa fa-chevron-left"></i></a>
    
  </div>
  <div class="pure-u-10-24">
    
    <nav class="prev">
      <a href="https://HauyuChen.github.io/post/%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%8E%92%E5%88%97/">字符串的排列</a>
    </nav>
    
  </div>
  <div class="pure-u-2-24">
    &nbsp;
  </div>
  <div class="pure-u-10-24">
    
    <nav class="next">
      <a href="https://HauyuChen.github.io/post/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9/">二叉树的下一个结点</a>
    </nav>
    
  </div>
  <div class="pure-u-1-24" style="text-align: right;">
    
    <a href="https://HauyuChen.github.io/post/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9/"><i class="fa fa-chevron-right"></i></a>
    
  </div>
</div>



  
<div id="disqus_thread"></div>
<script type="text/javascript">

(function() {
    
    
    if (window.location.hostname == "localhost")
        return;

    var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
    var disqus_shortname = "http-hov-space";
    dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
    (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com/" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>


</div>

</div>
</div>
<script src="https://HauyuChen.github.io/js/ui.js"></script>




</body>
</html>

