AI 助理
备案控制台
开发者社区 人工智能 文章 正文

一道算法题的分析

2018-06-27 1018
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
日志服务 SLS，月写入数据量 50GB 1个月
简介： 一位前辈发给我一道算法题，这里整理一下自己的解题思路。请设计一种处理算法能高效的检查出字符串中第一次出现的重复字符。给定的字符串长度小于等于500个字符，包含字母、数字、英文符号。

一位前辈发给我一道算法题，这里整理一下自己的解题思路。

请设计一种处理算法能高效的检查出字符串中第一次出现的重复字符。给定的字符串长度小于等于500个字符，包含字母、数字、英文符号。

img_5c370a85d8820764d65f1a2287ef0097.png
查找

解

查找第一次出现的重复字符...

  1. 逐个遍历字符，判断当前字符之前的字符数组中是否出现此字符，第一次出现则跳出循环

考察：在字符数组中如何快速的查找某个字符。

知识：

  • 字符是Java中的原始(Primitive)类型，可以和int类型直接转换的。它的包装类为Character.
  • 要查找字符数组是无序的，要不要对无序数组进行排序？不需要排序：排序算法最快的时间复杂度也为O(nlogn)，而遍历一遍的时间复杂度为O(n)，所以如果只进行一次操作，排序不如遍历。
  • 如果能进行O(1)，或者比O(1)略差一点的操作就好了，可以考虑使用HashMap，HashSet直接取值,HashMap内部使用数组来存储数据。

实现

  1. 普通版本，因为看到字符串长度小于500个字符，查找重复的字符，数据量比较小，普通的两层循环在数据量小的时候也可以尝试。时间复杂度为O(n^2)
    /**
     * 常规的查找第一个重复字符串的方法
     * @return 当字符串为空时，返回null
     */
    public static Character normalFind(String str){

        if (str == null || "".equals(str)) {
            return null;
        }

        if (str.length() > 500){
            //日志，根据文档，判断是否处理大字符串
            System.out.println("warn 输入的字符长度过大");
        }

        for (int i = 1; i < str.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (str.charAt(j) == str.charAt(i)){
                    return str.charAt(i);
                }
            }
        }
        return null;
    }
  1. 剥离HashMap实现部分，自己实现HashMap内部的数组存取，数据量比较小，采用简化的链表。
  • 考虑到数据量是在是太小的时候，这里阈值设置为15,长度小于15时使用常规的查找来操作，省的创建对象分配空间
  • 可设置内部要索引的数组容量。

依次遍历每个字符，遍历过的字符进行hashCode，字符的hashCode为自身代表的int值，hashCode与数组容量求余，将字符再以链表的形式存在数组中，如果其它字符的求出的下标重复，将当前节点加入到链表的最后节点。

    static class Node {
        /**
         * 存放下个节点
         */
        Node next;

        /**
         * 存放当前节点的值
         */
        int value;

        public Node() {
        }

        public Node(Node next, int value) {
            this.next = next;
            this.value = value;
        }

    }

      public static Character myFind(String str, Integer capacity) {
        if (str == null || "".equals(str)) {
            return null;
        }
        if (str.length() > 500) {
            //日志，根据说明判断是否处理
            System.out.println("warn 输入的字符长度过大");
        }
        if (str.length() <= 15) {
            return normalFind(str);
        }
        if (capacity == null){
            capacity = 16;
        }
        if (capacity >= 500){
            capacity = 500;
        }

        Node[] chars = new Node[capacity];
        for (int i = 0; i < str.length(); i++) {
            char tmpChar = str.charAt(i);
            //采用求余的方式，暂时不考虑使用位“与”操作
            int index = tmpChar % capacity;
            if (chars[index] != null) {
                //判断元素是否存在
                Node node = chars[index];
                while (true) {
                    if (node.value == tmpChar) {
                        return tmpChar;
                    }
                    if (node.next == null){
                        break;
                    }
                    node = node.next;
                }
                node.next = new Node(null, tmpChar);

            } else {
                chars[index] = new Node(null, tmpChar);
            }
        }
        return null;
    }
  1. 采用HashSet，Java内置数据结构进行数据的存取

如果待查找的字符数组中不存在字符，就加入新的字符，如果存在字符就返回当前字符

    public static Character setFind(String str) {
        if (str == null || "".equals(str)) {
            return null;
        }

        if (str.length() > 500) {
            //日志，根据说明判断是否处理
            System.out.println("warn 输入的字符长度过大");
        }

        HashSet<Character> hashSet = new HashSet<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (hashSet.contains(c)) {
                return c;
            } else {
                hashSet.add(c);
            }
        }
        return null;
    }

测试结果

测试代码如下：

 /**
     * 1. 字符类型为数字，字母，特殊字符
     * 2. 数组时连续的内存空间，可以直接根据下标来查找元素
     * 3. 计算机对数字比对字符敏感，因此字符的存储采用数字形式
     */
  public static void main(String[] args) {
        if (args.length == 0) {
            System.out.println("请在运行时输入字符串");
            return;
        }

        for (int i = 0; i < args.length; i++) {
            String str = args[i];
            System.out.println("待查找的字符串为：" + str);
            long normalStartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.normalFind(str));
            long normalEndtime = System.nanoTime();
            System.out.println("普通查找耗时：" + new BigDecimal(normalEndtime - normalStartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            long mytartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.myFind(str,16));
            long myEndtime = System.nanoTime();
            System.out.println("我的算法排序：容量16耗时：" + new BigDecimal(myEndtime - mytartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            mytartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.myFind(str,32));
            myEndtime = System.nanoTime();
            System.out.println("我的算法排序：容量32耗时：" + new BigDecimal(myEndtime - mytartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            mytartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.myFind(str,64));
            myEndtime = System.nanoTime();
            System.out.println("我的算法排序：容量64耗时：" + new BigDecimal(myEndtime - mytartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            long settartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.setFind(str,16));
            long setEndtime = System.nanoTime();
            System.out.println("set查找耗时:容量16：" + new BigDecimal(setEndtime - settartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            settartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.setFind(str,32));
            setEndtime = System.nanoTime();
            System.out.println("set查找耗时：容量32：" + new BigDecimal(setEndtime - settartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            settartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.setFind(str,64));
            setEndtime = System.nanoTime();
            System.out.println("set查找耗时：容量64：" + new BigDecimal(setEndtime - settartTime).divide(BigDecimal.valueOf(1000000)) + "ms");
            System.out.println("\n");
        }
    }

编译运行程序

javac me/aihe/exam/FindFirstRepeatdChar.java

运行程序：


img_080e9b0c18a9be6b66941f6991b8dad5.png
image.png

暂时只用了两个长度的字符串测试，可以多运行几次查看效果, 一般耗时和字符串的长度与指定的数组容量有关。

分析

  • 这次写的算法是牺牲空间来换取时间，普通的按顺序逐个对比不需要额外的空间。
  • 算法参考HashMap内部实现，但对其做了一些精简处理，Node节点这次存储的是字符字符的hashCode值，字符与int可以互相转换，Node只存储值就好了。
  • 省去了HashMap的resize()操作，直接在查找的时候指定数组的容量。数组的空间越大越不容易产生下标冲突，可以直接进行O(1)取出数据。

最后

最近越来越意识到算法的重要性，也在恶补中，稳扎稳打，希望能早日实现目标。

附录

完整代码：

package me.aihe.exam;

import java.math.BigDecimal;
import java.util.HashSet;

/**
 * @author aihe 2018/6/27
 */
public class FindFirstRepeatdChar {


    static class Node {
        /**
         * 存放下个节点
         */
        Node next;

        /**
         * 存放当前节点的值
         */
        int value;

        public Node() {
        }

        public Node(Node next, int value) {
            this.next = next;
            this.value = value;
        }

    }

    /**
     * 普通的查找第一个重复字符串的方法
     *
     * @return
     */
    public static Character normalFind(String str) {

        if (str == null || "".equals(str)) {
            return null;
        }

        if (str.length() > 500) {
            //日志，根据说明判断是否处理
            System.out.println("warn 输入的字符长度过大");
        }
        //从第一个下标开始找
        for (int i = 1; i < str.length(); i++) {

            for (int j = 0; j < i; j++) {
                if (str.charAt(j) == str.charAt(i)) {
                    return str.charAt(i);
                }
            }
        }
        return null;
    }

    public static Character myFind(String str, Integer capacity) {
        if (str == null || "".equals(str)) {
            return null;
        }
        if (str.length() > 500) {
            //日志，根据说明判断是否处理
            System.out.println("warn 输入的字符长度过大");
        }
        if (str.length() <= 15) {
            return normalFind(str);
        }
        if (capacity == null){
            capacity = 16;
        }
        if (capacity >= 500){
            capacity = 500;
        }

        Node[] chars = new Node[capacity];
        for (int i = 0; i < str.length(); i++) {
            char tmpChar = str.charAt(i);
            //采用求余的方式，暂时不考虑使用位“与”操作
            int index = tmpChar % capacity;
            if (chars[index] != null) {
                //判断元素是否存在
                Node node = chars[index];

                while (true) {
                    if (node.value == tmpChar) {
                        return tmpChar;
                    }
                    if (node.next == null){
                        break;
                    }
                    node = node.next;
                }
                node.next = new Node(null, tmpChar);

            } else {
                chars[index] = new Node(null, tmpChar);
            }
        }
        return null;
    }

    /**
     * 使用Java内置的hashset进行元素操作。
     * @param str
     * @return
     */
    public static Character setFind(String str,Integer capacity) {
        if (str == null || "".equals(str)) {
            return null;
        }

        if (str.length() > 500) {
            //日志，根据说明判断是否处理
            System.out.println("warn 输入的字符长度过大");
        }

        if (capacity == null){
            capacity = 16;
        }

        if (capacity >= 500){
            capacity = 500;
        }
        HashSet<Character> hashSet = new HashSet<>(capacity);
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (hashSet.contains(c)) {
                return c;
            } else {
                hashSet.add(c);
            }
        }
        return null;
    }


    /**
     * 1. 字符类型为数字，字母，特殊字符
     * 2. 数组时连续的内存空间，可以直接根据下标来查找元素
     * 3. 计算机对数字比对字符敏感，因此字符的存储采用数字形式
     */
    public static void main(String[] args) {
        //String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789!@#$%^&*()_+,./<>?[]{}交换代码由学会制定单符编方案基文本数据。起始于后期年最初是美家供不同计算机在相互通信时用作共遵守的西字它已被国际标准化组织定为国际标准，称为ISO 646标准。适用于所有拉丁文字字母";
        if (args.length == 0) {
            System.out.println("请在运行时输入字符串");
            return;
        }

        for (int i = 0; i < args.length; i++) {
            String str = args[i];
            System.out.println("待查找的字符串为：" + str);
            long normalStartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.normalFind(str));
            long normalEndtime = System.nanoTime();
            System.out.println("普通查找耗时：" + new BigDecimal(normalEndtime - normalStartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            long mytartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.myFind(str,16));
            long myEndtime = System.nanoTime();
            System.out.println("我的算法排序：容量16耗时：" + new BigDecimal(myEndtime - mytartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            mytartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.myFind(str,32));
            myEndtime = System.nanoTime();
            System.out.println("我的算法排序：容量32耗时：" + new BigDecimal(myEndtime - mytartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            mytartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.myFind(str,64));
            myEndtime = System.nanoTime();
            System.out.println("我的算法排序：容量64耗时：" + new BigDecimal(myEndtime - mytartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            long settartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.setFind(str,16));
            long setEndtime = System.nanoTime();
            System.out.println("set查找耗时:容量16：" + new BigDecimal(setEndtime - settartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            settartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.setFind(str,32));
            setEndtime = System.nanoTime();
            System.out.println("set查找耗时：容量32：" + new BigDecimal(setEndtime - settartTime).divide(BigDecimal.valueOf(1000000)) + "ms");

            settartTime = System.nanoTime();
            System.out.println("查找结果为：" + FindFirstRepeatdChar.setFind(str,64));
            setEndtime = System.nanoTime();
            System.out.println("set查找耗时：容量64：" + new BigDecimal(setEndtime - settartTime).divide(BigDecimal.valueOf(1000000)) + "ms");
            System.out.println("\n");
        }
    }
}
文章标签：
日志服务
算法
存储
Java
关键词：
算法分析
相关实践学习
日志服务之使用Nginx模式采集日志
本文介绍如何通过日志服务控制台创建Nginx模式的Logtail配置快速采集Nginx日志并进行多维度分析。
t-2653405963-6-49480
目录
相关文章
众所周知
|
3月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践，Python算法复杂度分析一站式教程，助你轻松驾驭大数据挑战！
【10月更文挑战第4天】在大数据时代，算法效率至关重要。本文从理论入手，介绍时间复杂度和空间复杂度两个核心概念，并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)；快速排序平均时间复杂度为O(n log n)，空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略，帮助你在大数据挑战中游刃有余。
众所周知
96 3
风吹落叶花飘荡
|
5月前
|
人工智能 算法 BI
第一周算法设计与分析 D : 两面包夹芝士
这篇文章介绍了解决算法问题"两面包夹芝士"的方法，通过找出两个数组中的最大最小值，计算这两个值之间的整数个数，包括特判不存在整数的情况。
风吹落叶花飘荡
54 0
游客akle7anmklvj6
|
5天前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代，文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用，包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据（如文件名、大小、位置等），查找时间复杂度为O(1)，显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能，实际应用中需解决哈希冲突、动态扩容和线程安全等问题，以优化性能。
游客akle7anmklvj6
14 1
蓝易云
|
14天前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中，理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略，可以显著提高算法效率。在实际开发中，应该根据具体需求和场景，选择合适的优化方法，从而编写出高效、可靠的代码。
蓝易云
25 6
土木林森
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
67 1
aliyun0942992302
|
3月前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手，逐步深入到线程调度、矩阵分块、循环展开等关键细节，最后通过带入具体值的方式进一步解析复杂循环逻辑，展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
aliyun0942992302
105 2
梦笔生花伟
|
3月前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史，其由于结构简单、易于实现、鲁棒性好、可靠性高等特点，在机电、冶金、机械、化工等行业中应用广泛。
梦笔生花伟
62 0
众所周知
|
4月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿！Python 算法设计与分析实战，教你如何精准评估与优化！
在 Python 编程中，算法的性能至关重要。本文将带您深入了解算法复杂度的概念，包括时间复杂度和空间复杂度。通过具体的例子，如冒泡排序算法 (`O(n^2)` 时间复杂度，`O(1)` 空间复杂度)，我们将展示如何评估算法的性能。同时，我们还会介绍如何优化算法，例如使用 Python 的内置函数 `max` 来提高查找最大值的效率，或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外，还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践，您将能更高效地优化 Python 程序。
众所周知
75 4
东方睿赢
|
4月前
|
算法 程序员 Python
程序员必看！Python复杂度分析全攻略，让你的算法设计既快又省内存！
在编程领域，Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而，性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析，从时间与空间复杂度入手，分享四大最佳实践：选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整，助你写出高效且节省内存的代码，轻松应对各种编程挑战。
东方睿赢
80 1
软件算法开发
|
4月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析（SSA）是一种基于奇异值分解（SVD）和轨迹矩阵的非线性、非参数时间序列分析方法，适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线，并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构，适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
软件算法开发
239 19

热门文章

最新文章

  • 1
    深入解析PID控制算法：从理论到实践的完整指南
  • 2
    猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
  • 3
    利用Python内置函数实现的冒泡排序算法
  • 4
    用 Python 实现快速排序算法。
  • 5
    深入解析图神经网络：Graph Transformer的算法基础与工程实践
  • 6
    【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
  • 7
    马特赛特旋转算法：Python的随机模块背后的力量
  • 8
    基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
  • 9
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 10
    基于GA遗传算法的PID控制器参数优化matlab建模与仿真
  • 1
    主流的目标检测算法是那种？
    69
  • 2
    [数据结构]——算法的时间复杂度和空间复杂度
    81
  • 3
    【软件设计师】通俗易懂的去了解算法的特性和要求
    75
  • 4
    记一次雪花算法遇到的 生产事故！
    261
  • 5
    图像的压缩算法--尺寸压缩、格式压缩和品质压缩
    164
  • 6
    【算法基础】基础算法（三）--（双指针算法、位运算、离散化、区间合并）
    40
  • 7
    【算法基础】基础算法（二）--（高精度、前缀和、差分）（下）
    40
  • 8
    【算法基础】基础算法（二）--（高精度、前缀和、差分）（上）
    48
  • 9
    【算法基础】基础算法（一）--（快速排序、归并排序、二分）
    39
  • 10
    常见排序算法及其稳定性分析
    84

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅