高頻考題！數(shù)組中找重復(fù)數(shù)字（算法 NO.1）
本題來自 LeetCode 中國網(wǎng)站，屬于算法面試中的一道經(jīng)典高頻考題。題解由 Doocs 開源社區(qū) leetcode 項(xiàng)目維護(hù)者提供。
目前已經(jīng)有超過 50 位開發(fā)者參與了此項(xiàng)目，期待你的加入！
項(xiàng)目地址：https://github.com/doocs/leetcode
題目描述
找出數(shù)組中重復(fù)的數(shù)字。
在一個(gè)長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。
示例 1：
輸入：[2, 3, 1, 0, 2, 5, 3]輸出：2 或 3
限制：
2 <= n <= 100000解法
0～n-1 范圍內(nèi)的數(shù)，分別還原到對應(yīng)的位置上，如：數(shù)字 2 交換到下標(biāo)為 2 的位置。
若交換過程中發(fā)現(xiàn)重復(fù)，則直接返回。
Python3
class Solution:def findRepeatNumber(self, nums: List[int]) -> int:for i, num in enumerate(nums):while i != num:if num == nums[num]:return numnums[i], nums[num] = nums[num], nums[i]num = nums[i]return -1
Java
class Solution {public int findRepeatNumber(int[] nums) {for (int i = 0, len = nums.length; i < len; ++i) {while (i != nums[i]) {if (nums[i] == nums[nums[i]]) {return nums[i];}swap(nums, i, nums[i]);}}return -1;}private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}}
長按識別下圖二維碼，關(guān)注公眾號「Doocs開源社區(qū)」，第一時(shí)間跟你們分享好玩、實(shí)用的技術(shù)文章與業(yè)內(nèi)最新資訊。
評論
圖片
表情