首页 > 其他分享 >287. 寻找重复数

287. 寻找重复数

时间:2023-05-15 22:56:01浏览次数:47  
标签:数字 nums 重复 示例 寻找 整数 int 287

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

 

示例 1:

输入:nums = [1,3,4,2,2]
输出:2

示例 2:

输入:nums = [3,1,3,4,2]
输出:3

 

提示:

    1 <= n <= 105
    nums.length == n + 1
    1 <= nums[i] <= n
    nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

 

题解:

哪个公司的面试题来着,我忘了。。。

就是求存在环的列表的环起点。

注意下标要从0开始看

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // 因为从0开始,所以就算有局部环,也走不到
        // 因为局部环的数字已经覆盖了相应区间的所有
        // 如果0走到,那么下标0所在位置的数字一定是重复的
        // 所以从0开始,一定能走到有重复数字的环

        int p = 0, q = 0;
        p = nums[p];
        q = nums[nums[q]];
        while(p != q)
        {
            p = nums[p];
            q = nums[nums[q]];
        }
        p = 0;
        while(p != q)
        {
            p = nums[p];
            q = nums[q];
        }
        return p;
    }
};

 

标签:数字,nums,重复,示例,寻找,整数,int,287
From: https://www.cnblogs.com/WTSRUVF/p/17403384.html

相关文章

  • 使用优先队列寻找中位数
    Next,SupposewewouldliketoinventanewADTcalledMedianFinderwhichisacollectionofintegersandsupportsfindingthemedianofthecollection.MedianFinderadd(x);//addsxtothecollectionofnumbersmedian();//returnsthemedianfromacol......
  • 给定一个字符串,用java代码找出其中不含有重复字符的最长子串的长度
    publicintlengthOfLongestSubstring(Strings){intn=s.length(),ans=0;Map<Character,Integer>map=newHashMap<>();for(inti=0,j=0;j<n;j++){if(map.containsKey(s.charAt(j))){i=Math.ma......
  • list删除重复数据
    方法一:循环元素删除//删除ArrayList中重复元素publicstaticvoidremoveDuplicate(Listlist){for(inti=0;i<list.size()-1;i++){for(intj=list.size()-1;j>i;j--){if(list.get(j).equals(list.get(i)))......
  • 剑指 Offer 03. 数组中重复的数字
    题目找出数组中重复的数字。在一个长度为n的数组nums里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。其中,2<=n<=100000示例输入:[2,3,1,0,2,5,3]输出:2或3......
  • 不重复的三位数
    一、问题描述: 二、设计思路: 三层循环,从1-4循环取值,条件判断每个位置上数字不相等   三、程序流程图:    四、代码实现:#include<stdio.h>intmain(){inta,b,c;intnum=0;inttemp;intcount=0;for(a=1;a<=4;a++){......
  • LeetCode 1047. 删除字符串中的所有相邻重复项
    题目链接:LeetCode1047.删除字符串中的所有相邻重复项题意:给出由小写字母组成的字符串S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。在S上反复执行重复项删除操作,直到无法继续删除。解题思路:开一个栈,然后扫描整个字符串。如果当前字符和栈顶元素不相等,则当前......
  • 【计算几何】Rust求解平面最近点对(寻找距离最近的两个点的距离)
    目录题目地址代码题目地址https://ac.nowcoder.com/acm/contest/52826/C代码usestd::io;usestd::cmp::Ordering;usestd::f64;#[derive(Debug,PartialEq,PartialOrd,Clone,Copy)]structPoint{x:f64,y:f64,}fneuclidean_distance(p1:&Point,p2:......
  • 双指针——最长连续不重复子序列(例)
    给定一个长度为n的整数序列,找出最长的不包含重复的数的连续区间,输出它的长度。数据范围: 输入样例:512235输出样例:3 #include<iostream>//C++标准库中的头文件.用于控制台输入和输出。#include<cstring>//用于处理字符串的函数和操作#include<algorithm>/......
  • 三菱FX3U模拟量FB函数块,使用结构化工程编写,FB块全部用ST语言编写,支持重复调用。
    三菱FX3U模拟量FB函数块,使用结构化工程编写,FB块全部用ST语言编写,支持重复调用。现在测试FX3U4DAFB块与数学量转工程量FB块,已正常没有问题。没有全部实物,其他功能块没有测试,有实物的朋友拿去测试!全部FB块如下:第一,FX2N-2DA模拟量输出FB函数块,第二,FX2N-2AD模拟量输入FB函数块,第三,FX......
  • 【二分查找】LeetCode 162. 寻找峰值思路
    题目链接162.寻找峰值思路思路一个不严谨但是好理解的思路是:如果\(nums[mid]>nums[mid+1]\),那么\(nums[mid+1]\)肯定不是峰值,此时让\(right=mid\),从左边继续找峰值。反之则\(nums[mid]\)肯定不为峰值,让\(left=mid+1\)。代码classSolution{public......