美文网首页
算法-如何查找第一个只出现一次的字符

算法-如何查找第一个只出现一次的字符

作者: zzq_nene | 来源:发表于2020-07-27 22:50 被阅读0次

方式一:

遍历每一个字符,然后取出遍历的当前字符与剩下的字符做比较,判断剩下的字符串中是否有当前遍历的这个字符,如果没有,则是在字符串中出现一次的,而第一个出现的,就是要查找的。

    /**
     * 使用便利的方式,时间复杂度是O(n^2)
     * @param str
     */
    private static void printFirstCharOnlyOnce(String str) {
        for (int i = 0; i < str.length(); i++) {
            // 截去第i个字符
            String temp = str.substring(0, i) + str.substring(i + 1);
            // 判断截去第i个字符后剩下的字符串中是否还有与第i个字符相同的字符
            int index = temp.indexOf(str.charAt(i));
            // 如果剩下的字符中没有与第i个字符相同的字符存在,则返回-1
            // 第一次出现index=-1的时候,说明第i个字符就是第一个出现一次的字符
            if (index == -1) {
                String c = String.valueOf(str.charAt(i));
                System.out.println(c);
                break;
            }
        }
    }

方式二:

直接使用hash表来查询,即使用HashMap来实现;首先遍历字符串的每一个字符,将字符作为HashMap的key,然后使用Integer作为HashMap的value,当key相同的时候,value就加1。遍历完之后,再对HashMap做遍历,找出key对应的value=1的key,第一个key就是查找第一个只出现一次的字符

    /**
    * 时间复杂度为O(n)
    */
    private static void printFirstCharOnlyOnce(String str) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            if (hashMap.containsKey(str.charAt(i))) {
                int value = hashMap.get(str.charAt(i));
                hashMap.put(str.charAt(i), value + 1);
            } else {
                hashMap.put(str.charAt(i), 1);
            }
        }

        for (int i = 0; i < str.length(); i++) {
            if (hashMap.get(str.charAt(i)) == 1) {
                System.out.println(str.charAt(i));
                break;
            }
        }
    }

方式三:

借助ASCII码,将字符的ASCII码作为在int数组的索引位置,而该字符出现的次数就是对应的int数组的索引位置的值

    private static void printFirstCharOnlyOnce(String str) {
        int[] hash = new int[256];
        for (int i = 0; i < str.length(); i++) {
            int temp = str.charAt(i);
            hash[temp]++;
        }

        for (int i=0;i<str.length();i++) {
            int temp = str.charAt(i);
            if (hash[temp] == 1) {
                System.out.println(str.charAt(i));
                break;
            }
        }
    }

相关文章

  • iOS算法

    算法 字符串翻转 单链表反转 有序数组合并 hash查找第一个只出现一次的字符

  • 2018-08-09

    字符串反转 链表反转(头差法) 有序数组合并 查找第一个只出现一次的字符(Hash查找) 查找两个子视图的共同父视...

  • 算法-如何查找第一个只出现一次的字符

    方式一: 遍历每一个字符,然后取出遍历的当前字符与剩下的字符做比较,判断剩下的字符串中是否有当前遍历的这个字符,如...

  • iOS 面试全方位剖析 -- 算法篇

    Hash 算法 所在一个字符串中找到第一个只出现一次的字符如:输入"sadagqeqsf" ,则输出 d。 算法思...

  • iOS 面试全方位剖析 -- 算法篇

    Hash 算法 所在一个字符串中找到第一个只出现一次的字符如:输入"sadagqeqsf" ,则输出 d。 算法思...

  • 字符篇

    1、第一个只出现一次的字符 问题描述:在字符串中找出第一个只出现一次的字符,如输入‘bacbd’,输出‘a’。要求...

  • KMP算法文章合集

    字符串的查找:朴素查找算法和KMP算法 暴力匹配算法与KMP算法(串的匹配) 字符串查找算法BF和KMP 字符串匹...

  • LeetCode 每日一题 [64] 第一个只出现一次的字符

    LeetCode 第一个只出现一次的字符 [简单] 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个...

  • 面试题50. 第一个只出现一次的字符

    第一个只出现一次的字符 题目描述 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 示例: ...

  • 面试题50(1):第一次只出现一次的字符

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

网友评论

      本文标题:算法-如何查找第一个只出现一次的字符

      本文链接:https://www.haomeiwen.com/subject/uoatrktx.html