文档章节

剑指OFFER(java)-数组中重复的数字

一贱书生
 一贱书生
发布于 2016/08/08 15:45
字数 1454
阅读 14
收藏 0
点赞 0
评论 0

题目:在一个长度为n的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

 

题目分析

解决这个问题的一个简单的方法是先把输入的数组排序。从排序的数组中找出重复的数字时间很容易的事情,只需要从头到尾扫描排序后的数组就可以了。排序一个长度为 n 的数组需要 O(nlogn)的时间。

还可以利用哈希表来解决这个问题。从头到尾按顺序扫描数组的每个数,每扫描一个数字的时候,都可以用 O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字,就把它加入到哈希表里。如果哈希表里已经存在该数字了,那么就找到一个 重复的数字。这个算法的时间复杂度是 O(n),但它提高时间效率是以一个大小为 O(n)的哈希表为代价的。我们再看看有没有空间复杂度为 O(1)的算法。

我们注意到数组中的数字都在 0 到 n-1 中。如果这个数组中没有重复的数字,那么当数组排序之后数字 i 将出现在下标为 i 的位置。由于数组中有重复的数字,有些位置可能存在多个数字,同时有些位置可能没有数字。

现在让我们重排这个数组,依然从头到尾一次扫描这个数组中的每个数字。当扫描到下标为 i 的数字时,首先比较这个数字(用 m 表示)是不是等于 i。如果是,接着扫描下一个数字。如果不是,再拿它和第 m 个数字进行比较。 如果它和第m个数字相等,就找到了一个重复的数字(该数字在下标为 i 和 m 的位置都出现了)。如果它和第 m 个数字不相等,就把第 i 个数字和第 m 个数字交换,把 m 放到属于它的位置。接下来再重读这个比较、交换的过程,直到我们发现一个重复的数字。

以数组{2,3,1,0,2,5,3}为例来分析找到重复数字的步骤。数组的第 0 个数字(从 0 开始计数,和数组的下标保持一致)是 2,与它的下标不相等,于是把它和下标为 2 的数字 1 交换。交换之后的数组是{1.3.2.0.2.5.3}。此时第 0 个数字是 1,仍然与它的下标不相等,继续把它和下标为 1 的数字 3 交换,得到数组{3,1,2,0,2,5,3}.接下来继续交换第 0 个数字 3 和第 3 个数字 0,得到数组{0,1,2,3,2,5,3}。此时第 0 个数字的数值为 0,接着扫描下一个数字。在接下来的几个数字中,下标为 1,2,3 的三个数字分别为 1,2,3 它们的下标和数值都分别相等,因此不需要做任何操作。接下来扫描到下标为 4 的数字 2。由于它的数值与它的下标不相等,再比较它和下标为 2 的数字。注意到此时数组中下标为 2 的数字也是 2,也就是数字在下标为 2 和下标为 4 的两个位置都出现了,因此找到一个重复的数字。

1、哈希实现:

package cglib;

import java.util.HashMap;
import java.util.Map;

public class jiekou {

    
     public int duplicate(int numbers[],int length,int [] duplication) {
            //异常处理
            if(numbers == null || numbers.length <= 1 || length <= 1)
                return -1;
            //创建一个HashMap保存每个数字出现的次数
            Map<Integer,Integer> counter = new HashMap<Integer, Integer>();
            for(int i = 0; i < length; i++){
                if(counter.containsKey(numbers[i])){
                    //duplication[0] = numbers[i];
                    //return true;
                    return numbers[i];
                }else{
                    counter.put(numbers[i], new Integer(1));
                }
            }
            return -1;
        }

        public static void main(String[] args) {
            int [] numbers = {4,4,1,0,1,5,3};
            int f = new jiekou().duplicate(numbers, 7, new int[1]);
            System.out.println(f);
        }
    }
   

 

输出:4

 

下面的代码中尽管有一两个重复需要交换,但每个数字最多只要交换两次就能找到属于自己的位置,因此总的时间复杂度为O(n),另外,所有的操作步骤都是在输入数组上进行,不需要额外的分配内存,因此空间复杂度为O(1).

 

package cglib;


public class jiekou {
    /**
     * 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的,
     * 但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
     * 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者。
     *
     * @param number
     * @return
     */
    public static int duplicate(int[] number) {
        if (number == null || number.length < 1) {
            return -1;
        }
        // 判断输入的是否在[0, number.length-1]之间
        for (int i : number) {
            if (i < 0 || i >= number.length) {
                return -1;
            }
        }
    for (int i = 0; i < number.length; i++) {
        // 当number[i]与i不相同的时候一直交换
        while (number[i] != i) {
            // 如果i位置与number[i]位置的数字相同,说明有重复数字
            if (number[i] == number[number[i]]) {
                return number[i];
            }
            // 如果不同就交换
            else {
                swap(number, i, number[i]);
            }
        }
    }
    return -1;
}
private static void swap(int[] data, int x, int y) {
    int tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
}
public static void main(String[] args) {
    int[] numbers1 = {2, 1, 3, 1, 4};
    System.out.println(duplicate(numbers1));
    int[] numbers2 = {2, 4, 3, 1, 4};
    System.out.println(duplicate(numbers2));
    int[] numbers3 = {2, 4, 2, 1, 4};
    System.out.println(duplicate(numbers3));
    int[] numbers4 = {2, 1, 3, 0, 4,2,2};
    System.out.println(duplicate(numbers4));
    int[] numbers5 = {2, 1, 3, 5, 4};
    System.out.println(duplicate(numbers5));
}
    }

输出:

1
4
2
2
-1

 

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
飞龙的程序员书单 – 数据结构、算法

入门向 啊哈!算法 这本书真心简洁易懂,dijkstra我是看课本怎么看也看不懂,最后看这本书才懂的。真心推荐。 大话数据结构 工程向 算法 Java实现 C实现 C++实现 普林斯顿的算法课程教材,Cou...

apachecn_飞龙 ⋅ 2016/01/15 ⋅ 0

全面的java编程新手入门学习笔记总结

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/10 ⋅ 0

升级到JDK9的一个BUG,你了解吗

概述 前几天在一个群里看到一个朋友发了一个demo,说是JDK的bug,昨天在JVM的一个群里又有朋友发了,觉得挺有意思,分享给大家,希望大家升级JDK的版本的时候注意下是否存在这样的代码,如果...

你假笨 ⋅ 06/06 ⋅ 0

Android JNI学习(四)——JNI的常用方法的中文API

本系列文章如下: Android JNI(一)——NDK与JNI基础 Android JNI学习(二)——实战JNI之“hello world” Android JNI学习(三)——Java与Native相互调用 Android JNI学习(四)——JNI的常用方法...

隔壁老李头 ⋅ 05/09 ⋅ 0

tomcat中jvm内存溢出解决方案

常见的内存溢出有以下两种: java.lang.OutOfMemoryError: PermGen space java.lang.OutOfMemoryError: Java heap space 一、java.lang.OutOfMemoryError: PermGen space PermGen space的全称......

jin_6868 ⋅ 05/25 ⋅ 0

Android JNI(一)——NDK与JNI基础

本系列文章如下: Android JNI(一)——NDK与JNI基础 Android JNI学习(二)——实战JNI之“hello world” Android JNI学习(三)——Java与Native相互调用 Android JNI学习(四)——JNI的常用方法...

隔壁老李头 ⋅ 05/09 ⋅ 0

新浪、百度、好未来3offer到手全记录 | 牛客面经

新浪、百度、好未来3offer到手全记录 牛客面经 原创 2017-09-19 牛友 招聘消息汇总 渣渣的秋招之路 附上新浪,百度,好未来面经 作者:offer快到碗里来?。! 来源:牛客网 楼主是本科渣渣,...

公子只识黛玉 ⋅ 04/17 ⋅ 0

Java面试2018常考题目汇总及答案带走不谢!

一、JAVA基础篇-概念 1.简述你所知道的Linux: Linux起源于1991年,1995年流行起来的免费操作系统,目前, Linux是主流的服务器操作系统, 广泛应用于互联网、云计算、智能手机(Android)等...

java高级架构牛人 ⋅ 06/14 ⋅ 0

我所经历的Android面试|掘金技术征文

概述 时隔一个多月,我又回来了。这段时间有不少人问我最近在干嘛,面经什么时候写,怎么这么久没更文了等等等等。当然了,最近我一直在执行了一次我计划了近半年的跳槽。总得而言还不错。说...

我就是马云飞 ⋅ 04/21 ⋅ 0

JNI开发流程与引用数据类型的处理

今天我们来看下Java JNI,先看下维基百科给的定义, JNI, Java Native Interface, Java本地接口,是一种编程框架,使得Java虚拟机中的Java程序可以调用本地应用或库,也可以被其他程序调用。...

juexingzhe ⋅ 05/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 11分钟前 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

楠木楠 ⋅ 23分钟前 ⋅ 0

Python 数电表格格式化 xlutils xlwt xlrd的使用

需要安装 xlutils xlwt xlrd 格式化前 格式化后 代码 先copy读取的表格,然后按照一定的规则修改,将昵称中的学号提取出来替换昵称即可 from xlrd import open_workbookfrom xlutils.copy ...

阿豪boy ⋅ 52分钟前 ⋅ 0

面试题:使用rand5()生成rand7()

前言 读研究生这3 年,思维与本科相比变化挺大的,这几年除了看论文、设计方案,更重要的是学会注重先思考、再实现,感觉更加成熟吧,不再像个小P孩,人年轻时总会心高气傲。有1 道面试题:给...

初雪之音 ⋅ 52分钟前 ⋅ 0

Docker Toolbox Looks like something went wrong

Docker Toolbox 重新安装后提示错误:Looks like something went wrong in step ´Checking if machine default exists´ 控制面板-->程序与应用-->启用或关闭windows功能:找到Hyper-V,如果处......

随你疯 ⋅ 今天 ⋅ 0

Guacamole 远程桌面

本文将Apache的guacamole服务的部署和应用,http://guacamole.apache.org/doc/gug/ 该链接下有全部相关知识的英文文档,如果水平ok,可以去这里仔细查看。 一、简介 Apache Guacamole 是无客...

千里明月 ⋅ 今天 ⋅ 0

nagios 安装

Nagios简介:监控网络并排除网络故障的工具:nagios,Ntop,OpenVAS,OCS,OSSIM等开源监控工具。 可以实现对网络上的服务器进行全面的监控,包括服务(apache、mysql、ntp、ftp、disk、qmail和h...

寰宇01 ⋅ 今天 ⋅ 0

AngularDart注意事项

默认情况下创建Dart项目应出现以下列表: 有时会因为不知明的原因导致列表项缺失: 此时可以通过以下步骤解决: 1.创建项目涉及到的包:stagehand 2.执行pub global activate stagehand或pub...

scooplol ⋅ 今天 ⋅ 0

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部