一道劍指offer，找到重復的數(shù)字

今天給大家?guī)淼氖且坏绖χ竜ffer上的題目，也是一道很經典的題目，經常在面試中出現(xiàn)，題目很簡單，大家記得打卡呀。

下面我們來看一下題目描述

題目說明：在一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內。數(shù)組中某些數(shù)字是重復的，但不知道有幾個數(shù)字重復了，也不知道每個數(shù)字重復了幾次。請找出數(shù)組中任意一個重復的數(shù)字。

示例 1：

輸入：[2, 3, 1, 0, 2, 5, 3] 輸出：2 或 3

題目解析：該題題意很容易理解，只需要找出數(shù)組中的某一重復出現(xiàn)的數(shù)字即可。

排序遍歷法：

我們今天主要通過三種做法解決該題，第一種方法我們可以先對其排序，然后進行遍歷當發(fā)現(xiàn)重復元素時我們直接返回該元素即可，這種方法比較容易理解，也比較容易實現(xiàn)。

哈希表：

第二種方法就是借助我們的哈希表，遍歷數(shù)組，利用哈希表存儲遇到的數(shù)字，如果哈希表已經存儲過該數(shù)字則直接返回即可。這種方法也比較簡單。

下面我們來看代碼吧

原地置換：

下面我們看一下這個原地置換法，原地置換的總體思路就是將我們的元素放到他的索引位置。我們可以這樣理解，每個人都有自己的位置，我們需要和別人調換回到屬于自己的位置，調換之后，如果發(fā)現(xiàn)我們的位置上有人了，則返回。大致意思了解了，下面看代碼的執(zhí)行過程。

題目代碼：