前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LintCode 633. 寻找重复的数(这个题要复习)

LintCode 633. 寻找重复的数(这个题要复习)

作者头像
Michael阿明
发布2020-07-13 15:51:58
2580
发布2020-07-13 15:51:58
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

给出一个数组 nums 包含 n + 1 个整数,每个整数是从 1 到 n (包括边界),保证至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

代码语言:javascript
复制
样例 1:
输入:
[5,5,4,3,2,1]
输出:
5

样例 2:
输入:
[5,4,4,3,2,1]
输出:
4

注意事项 1.不能修改数组(假设数组只能读) 2.只能用额外的O(1)的空间 3.时间复杂度小于O(n2) 4.数组中只有一个重复的数,但可能重复超过一次

2. 解题

  • 把数值作为下标,跟下标处的数交换,直到相等为止
代码语言:javascript
复制
class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int i = 0;
        while(nums[i] != nums[nums[i]])
            swap(nums[i], nums[nums[i]]);
        return nums[i];
    }
};

or 位运算swap

代码语言:javascript
复制
class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int i = 0;
        while(nums[i] != nums[nums[i]])
            myswap(nums[i], nums[nums[i]]);
        return nums[i];
    }
    
    inline void myswap(int& a, int& b)
    {
        a ^= b ^= a ^= b;
    }
};

100% 数据通过测试 总耗时 1561 ms 您的提交打败了 90.80% 的提交!

  • 快慢指针
代码语言:javascript
复制
class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int fast = 0;
        int slow = 0;
        do
        {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        while(fast != slow);
        
        slow = 0;
        while (slow != fast) 
        {
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;
    }
};
  • 标记为负数法
代码语言:javascript
复制
class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int idx, i;
        for(i = 0; i < nums.size(); ++i)
        {
            idx = abs(nums[i]);
            if(nums[idx] > 0)
                nums[idx] = -nums[idx];
            else
                return idx;
        }
        return -1;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/03/10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档