新浦京网投站网止,澳门新浦京26999com

    欢迎访问澳门新浦京26999com~

  1. 加入收藏
  2. 设为主页
  3. 学校简介
北大青鸟

三分钟了解北大青鸟

×
  • 北大青鸟大数据课程
  • 北大青鸟网络工程师
  • 北大青鸟web设计专业
  • 北大青鸟PHP专业
  • 北大青鸟启蒙星课程

Java培训:寻找个只出现一次的字符

责任编辑:秩名来源:澳门新浦京26999comJava技术教程发布时间:2013-04-20 09:27
导读: 北大青鸟武汉宏鹏鲁广校区老师解读:寻找个只出现一次的字符

  北大青鸟武汉宏鹏鲁广校区老师解读:寻找个只出现一次的字符

       题目:在一个字符串中找到个只出现一次的字符。如输入abaccdeff,则输出b.

  分析:这道题是2006年google的一道笔试题。

  看到这道题时,直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。

  由于题目与字符出现的次数相关,我们是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数,也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中,哈希表正是这个用途。

  哈希表是一种比较复杂的数据结构。由于比较复杂,STL中没有实现哈希表,因此需要我们自己实现一个。但由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。由于字符(char)是一个长度为8的数据类型,因此总共有可能256 种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。

  我们遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了。

  1.初始化哈希数组,数组长度为256,每个元素都初试化为0

  2.从头遍历输入字符串,每碰到一个字符,以此字符的ascii码值为数组下标,在哈希表中找到对应的项并吧出现的次数加一次

  3.从头遍历输入字符串,每碰到一个字符,查看其在hash表中对应的下标是否为1,如果是,则返回该数组,否则继续循环

  [java]

  public class Test_13 {

  public static void main(String[] args) {

  String str = "baccdde";

  System.out.println(FindFirstNotRepeat(str));

  }

  public static char FindFirstNotRepeat(String str){

  if(str == null){

  System.out.println("输入为空!");

  return ' ';

  }

  int[] hash = new int[256];

  //初始化hash数组

  for(int i =0;i

  hash[i]=0;

  }

  for(int i =0;i

  hash[str.charAt(i)] ++;

  }

  for(int i=0;i

  if(hash[str.charAt(i)] == 1)

  return str.charAt(i);

  }

  return ' ';

  }

  }

 

本文标题:Java培训:寻找个只出现一次的字符,责任编辑:秩名,来源:北大青鸟武汉宏鹏鲁广校,于2013年04月20日09时27分发布于澳门新浦京26999com。新浦京网投站网止宏鹏鲁广校区,是北大青鸟武汉电脑学校,专业IT计算机培训,拥有软件/网络/安卓/Web前端/Java课程.北大青鸟地址:光谷广场鲁巷数码港.电话:027-87807717

专业老师指导

专业老师指导

赵老师

从事IT教育培训十年有余,致力于帮助广大学子找到适合自己的专业。

培训咨询客服

培训咨询客服

陈老师

IT培训专业客服,用自己的真诚解决了无数学子的困惑。

本文地址:
文章标题:
  • 北大青鸟Java软件开发
  • 北大青鸟UI设计课程_零基础可学
  • 北大青鸟动漫设计_武汉设计学校
  • 北大青鸟数字艺术_武汉电脑学校
在线咨询
×
在线咨询更多问题

如您有任何疑问
在线咨询随时为您解答或拨打咨询热线:17740513250

×
  • 姓 名*
  • 手 机*
  • QQ号/微信号
  • 所报学科 *
  • 其他备注
  • 温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一报名服务。