CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

    • 哈希表理论基础
    • 剑指 Offer 50 - 第一个只出现一次的字符
    • 验证外星语词典
    • 有效的字母异位词
    • 字母异位词分组
    • 单词长度的最大乘积
    • 两个数组的交集
    • 多个数组求交集
    • 赎金信
    • 快乐数
    • 两数之和
    • 四数相加 II
    • 最小时间差
    • 缺失的第一个正数
    • 最长连续序列
    • 剑指 Offer 03 - 数组中重复的数字
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 利用哈希表设计高级结构

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 哈希表
小牛肉
2022-09-22
目录

剑指 Offer 03 - 数组中重复的数字

# 📃 题目描述

题目链接:剑指 Offer 03. 数组中重复的数字 (opens new window)

# 🔔 解题思路

利用数据结构特点,容易想到使用哈希表(Set)记录数组的各个数字,当查找到重复数字则直接返回,这里就不贴代码了

题目说明在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义:数组元素的 索引 和 值 是 一对多 的关系。

因此,可遍历数组并通过交换操作,使元素的 索引 与 值 一一对应(即 nums[i] = inums[i]=i )。因而,就能通过索引映射对应的值,起到与字典等价的作用。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            int targetIndex = nums[i];
            // 当前 nums[i] 出现在正确的位置
            if (targetIndex == i) {
                i ++;
            } 
            else if (nums[targetIndex] != nums[i]) {
                swap(nums, i, targetIndex);
            } 
            // nums[targetIndex] == nums[i], 重复数字
            else {
                return nums[i];
            }
        }

        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
最长连续序列
插入、删除和随机访问都是 O(1) 的容器

← 最长连续序列 插入、删除和随机访问都是 O(1) 的容器→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式