首页 > 编程语言 >剑指offer03(Java)-数组中重复的数字(简单)

剑指offer03(Java)-数组中重复的数字(简单)

时间:2023-04-08 11:24:27浏览次数:57  
标签:Java offer03 nums int 索引 num 数组 专业对口 数字

题目:

找出数组中重复的数字。


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

示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
 

限制:

2 <= n <= 100000

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

方法一:哈希表

 1 class Solution {
 2     public int findRepeatNumber(int[] nums) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         for (int num : nums){
 5             map.put(num, map.getOrDefault(num, 0) + 1);
 6         }
 7         for (int num : map.keySet()){
 8             if (map.get(num) >= 2) return num;
 9         }
10         return -1;
11     }
12 }

 方法二:原地交换

利用题目已知条件:长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。表示出现的每个数字都可以找到每个索引。

看了K神评论区的老师解释

原地交换法就相当于分配工作,每个索引代表一个工作岗位,每个岗位必须专业对口,既0索引必须0元素才能上岗。而我们的目的就是找出溢出的人才,既0索引岗位有多个0元素竞争。

我们先从0索引岗位开始遍历,首先我们看0索引是不是已经专业对口了,如果已经专业对口既nums[0]=0,那我们就跳过0岗位看1岗位。如果0索引没有专业对口,那么我们看现在0索引上的人才调整到他对应的岗位上,比如num[0]=2,那我们就把2这个元素挪到他对应的岗位上既num[2],这个时候有两种情况:1、num[2]岗位上已经有专业对口的人才了,既num[2]=2,这就说明刚刚那个在num[0]上的2是溢出的人才,我们直接将其返回即可。2、num[2]上的不是专业对口的人才,那我们将num[0]上的元素和num[2]上的元素交换,这样num[2]就找到专业对口的人才了。之后重复这个过程直到帮num[0]找到专业对口的人才,然后以此类推帮num[1]找人才、帮num[2]找人才,直到找到溢出的人才。

算法思路:

从下标为0开始遍历数组nums,正常应该是nums[i] = i,如果下标为 i 的数字不是 i 的话,假设为temp,就将nums[temp] 与nums[i]进行交换。在交换的过程中,如果遇到重复数字,就将nums[i]进行返回即可。遍历完也没有返回值,直接返回-1。

 1 class Solution {
 2     public int findRepeatNumber(int[] nums) {
 3         for (int i = 0; i < nums.length; i++){
 4             while(nums[i] != i){
 5                 if (nums[nums[i]] == nums[i]){
 6                     return nums[i];
 7                 }
 8                 int temp = nums[i];
 9                 nums[i] = nums[temp];
10                 nums[temp] = temp;
11             }  
12         }
13         return -1;
14     }
15 }

 

标签:Java,offer03,nums,int,索引,num,数组,专业对口,数字
From: https://www.cnblogs.com/liu-myu/p/17295750.html

相关文章

  • 颜色分类(数组、双指针)、排列序列(递归、数学)、合并区间(数组、排序)
    颜色分类(数组、双指针)给定一个包含红色、白色和蓝色,一共n__个元素的数组,**原地(https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)**对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。此题中,我们使用整数0、1和2分别表示红色、......
  • JavaScript遍历数组用splice方法删除元素,这样写可能有遗漏,你遇到过吗?
    在编写“圳品”信息系统中,有时需要对二维数组中的数据进行筛选并删除一些元素,比如删除二维数组中首个元素为0的行。开始是用for循环访问数组+splice方法删除元素来做:vara=newArray([0,0,0,0],[1,1,1,1],[0,2,2,2],[......
  • 26. 删除有序数组中的重复项 & 80. 删除有序数组中的重复项 II
    力扣题目链接(26)给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重......
  • js数组对象如何改变里面对象键名
    方法二中,怎么就通过改变item,arr的值就直接改变了的呢?在JavaScript中,对象是引用类型,当你将一个对象赋值给一个变量时,实际上是将该对象的引用赋值给了变量,而不是复制了该对象本身letobj={name:'jack',age:23}letobj_son=obj;obj_son.name='tome'console.log(obj......
  • JavaScript的引入方式
    外部JS文件deno.jsalert('你好!JavaScript');JS引入方式.html<!--方式一:内部脚本--><!--标签不能自闭和--><script>alert('你好JS')</script><!--方式二:外部引入--><scriptsrc="demo.js"></script>......
  • Java方法
    Java方法方法是什么解决一类问题的步骤的有序组合System.out.print()-------------------System是一个类out是一个对象print()是一个方法方法是一个语句块集合,它们在一起执行一个功能设计原则:保持原子性,一个方法只完成一个功能方法的定义及调用Java只有值传递方法......
  • 一维数组的应用举例
    案例1从键盘读入学生成绩,找出最高分,并输出学生成绩等级成绩>=最高分-10等级为’A’成绩>=最高分-20等级为’B’成绩>=最高分-30等级为’C’其余等级为’D’提示:先读入学生人数,根据人数创建int数组,存放学生成绩。publicstaticvoidScoreTest(){//提示......
  • Java内存模型
    Java内存模型的作用《Java虚拟机规范》中曾试图定义一种“Java内存模型”(JavaMemoryModel,JMM)来屏蔽各种硬件和操作系统的内存访问差异,以实现让Java程序在各种平台下都能达到一致的内存访问效果。在此之前,主流程序语言(如C和C++等)直接使用物理硬件和操作系统的内存模......
  • 内存溢出:报错java.lang.OutOfMemoryError: PermGen space
    前言前后台调试过程中某个查询操作导致了后台报错java.lang.OutOfMemoryError:PermGenspace,百度了一下说是内存溢出,设置JVM参数就能解决,确实是如此。引用别人的解释:OutOfMemoryError:PermGenspace非堆溢出(永久保存区域溢出) 这种错误常见在web服务器对JSP进行pre......
  • javaEE进阶小结与回顾(二)
    内部类概述,在一个类里面再定义一个类,这个类称为内部类,外部的类称为外部类分类,成员内部类,局部内部类 成员内部类调用方法:方式一:通过外部类的方法,创建内部类对象方式二:第三方创建内部类对象------Outer.Inneroi=newOuter().newInner(); 修饰符private:只......