文档章节

IT公司100题-17-第一个只出现一次的字符

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/12/19 21:45
字数 230
阅读 94
收藏 8

问题描述:

在一个字符串中找到第一个只出现一次的字符。例如输入asdertrtdsaf,输出e。

 

分析:

最简单的方法是直接遍历,时间复杂度为O(n^2)。

进一步思考:

字符串中的字符,只有256种可能性,使用字符的为下标,扫描一遍,存储各个字符在字符串中的出现。第二次扫描字符串,查看每个字符在字符串中的出现次数,如果为1,输出即可。

代码实现:

package oschina.IT100;

/**
 * @project: oschina
 * @filename: iT17.java
 * @version: 0.10
 * @author: JM Han
 * @date: 12:54 2015/12/19
 * @comment: find the 1st char that only exist once in string
 * @result:
 */

public class iT17 {
   public static Character findChar(String s){
      int[] int_set = new int[256];
      char[] char_set = s.toCharArray();
      for(char c: char_set){
         int_set[c]++;
      }
      for(char c: char_set){
         if(int_set[c] == 1)
            return c;
      }
      return '\0';
   }
   public static void main(String[] args) {
      System.out.println("The 1st char is: " + findChar("asdertrtdsaf"));
   }
}


© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
加载中

评论(2)

关西大汉弹琵琶
关西大汉弹琵琶 博主

引用来自“xianren_2013”的评论

使用哈希表是,以字符串为键值,出现次数为值。
遍历字符串,如果出现次数大于1,则删除键。
当遍历完字符串后,哈希表中存在的键,即为出现一次的字符
xianren_2013
xianren_2013
使用哈希表是,以字符串为键值,出现次数为值。
遍历字符串,如果出现次数大于1,则删除键。
当遍历完字符串后,哈希表中存在的键,即为出现一次的字符
剑指offer 54. 字符流中第一个不重复的字符

题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第...

dby_freedom
2018/11/25
0
0
ls 排序

root@python-develpment:/mo# ls -l | sort -n -t '_' -k 2 | more drwx------ 2 root root 12288 11 17 08:59 lost+found -rw-r--r-- 1 root root 0 11 17 09:02 1 ×üóá 12 -rw-r--r-- ......

Love轩轩
2017/11/17
0
0
经典算法学习——第一个只出现一次的字符

这同样是剑指Offer中的很经典的一道面试题。题目描述为:在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”,则输出'b'. 一开始大家就会想到最简单的方法就是每访问到一个字符的时...

chenyufeng1991
2016/08/21
0
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
串联所有单词的子串

原题   You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each ......

一贱书生
2016/12/14
54
0

没有更多内容

加载失败,请刷新页面

加载更多

面试官,Java8 JVM内存结构变了,永久代到元空间

在文章《JVM之内存结构详解》中我们描述了Java7以前的JVM内存结构,但在Java8和以后版本中JVM的内存结构慢慢发生了变化。作为面试官如果你还不知道,那么面试过程中是不是有些露怯?作为面试...

程序新视界
11分钟前
8
0
读书笔记:深入理解ES6 (八)

第八章 迭代器(Iterator)与生成器(Generator) 第1节 循环语句的问题   在循环、多重循环中,通过变量来跟踪数组索引的行为容易导致程序出错。迭代器的出现旨在消除这种复杂性,并减少循...

张森ZS
11分钟前
8
0
Elasticsearch 实战(一) - 简介

官腔 Elasticsearch,分布式,高性能,高可用,可伸缩的搜索和分析系统 基本等于没说,咱们慢慢看 1 概述 百度:我们比如说想找寻任何的信息的时候,就会上百度去搜索一下,比如说找一部自己喜...

JavaEdge
16分钟前
8
0
【jQuery基础学习】11 jQuery性能简单优化

本文转载于:专业的前端网站➦【jQuery基础学习】11 jQuery性能简单优化 关于性能优化 合适的选择器 $("#id")会直接调用底层方法,所以这是最快的。如果这样不能直接找到,也可以用find方法继...

前端老手
25分钟前
7
0
重磅发布 | 全球首个云原生应用标准定义与架构模型 OAM 正式开源

导读:2019 年 10 月 17 日,阿里巴巴合伙人、阿里云智能基础产品事业部总经理蒋江伟(花名:小邪)在 Qcon 上海重磅宣布,阿里云与微软联合推出开放应用模型 Open Application Model (OAM...

阿里云官方博客
27分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部