程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Find the Duplicate Number

leetcode筆記:Find the Duplicate Number

編輯:關於C++

一. 題目描述

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate element must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).
You must use only constant extra space.
Your runtime complexity should be less than O(n^2).
There is only one duplicate number in the array, but it could be repeated more than once.

二. 題目分析

題目的大意是,給定一個包含n + 1個整數的數組,其中每一個整數的大小均在[1, n]之間,證明其中至少有一個重復元素存在。同時假設數組中只有一個數字出現重復,找出這個重復的數字。

注意事項:

不可以修改數組(假設數組是只讀的) 只能使用常數空間 運行時間復雜度應該小於O(n^2) 數組中只存在一個重復數,但是該數可能重復多次

題目的限定要求非常多,一開始並不能想到最優方法,這裡給出一種新穎的方法:映射找環法,其實這種方法來源於鏈表找環。時間復雜度為O(n),空間復雜度O(1)

首先,假設一個數組中沒有重復,則可以將數組的下標和其對應元素(1 ~ n)一一的映射起來。舉個例子,對於數組[4, 1, 3, 2],則映射關系為0 -> 4, 1 -> 1, 2 -> 3,3 -> 2

這個映射關系可表示一個函數f(n),其中n是下標,f(n)是映射到的數。如果我們從下標為0出發,根據這個函數計算出一個值,以這個值為新的下標,再用這個函數計算,以此類推,可以產生一個類似於鏈表的序列。

此時,如果數組本身有重復的元素,就會出現多對一的映射,比如數組[2, 1, 3, 1],則映射關系為:0 -> 2, {1, 3} -> 1, 2 -> 3。熟悉鏈表的朋友知道,這一序列中出現了環路!與鏈表一致,如果遍歷這個映射關系:0 -> 2 -> 3 -> 1 -> 1 -> 1 -> ...,其中,環的起點就是題目所要求的重復的數。

所以該題實際上可轉化為求環路起點,實現方法與Linked List Cycle II一題類似。同樣,使用快慢(fastslow)兩個下標,從0開始,快下標每次循環時映射兩次,即:fast = num[num[fast]],而慢下標每次循環映射一次,即:slow = num[slow],直到fast == slow,這個階段相當於鏈表找環時,快指針與慢指針相遇,這一結論證明鏈表有環,對應到本題中,則能證明數組內有重復元素!

第二步,是找出這個重復元素,也就是找出環的入口,這時需要另一個變量finder從下標0出發,和fast的操作一致,每次循環映射兩次:fast = num[num[fast]],同時,slow保持一次映射。當這兩個下標相遇時,slow就是環的起點,也就是重復的數。

三. 示例代碼

class Solution {
public:
    int findDuplicate(vector& nums) {
        int slow = 0;
        int fast = 0;
        int finder = 0;

        while (true)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];

            if (slow == fast)
                break;
        }

        while (true)
        {
            slow = nums[slow];
            finder = nums[finder];
            if (slow == finder)
                return slow;
        }
    }
};

四. 小結

該題的思路相當新穎,不容易想到,此外,還有使用二分法來解決的方案,但不是最優方案。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved