??前面的話??
大家好！博主開辟了一個新的專欄——劍指offer，我要開始刷題了！這個專欄會介紹《劍指offer》書上所有的面試編程題，并且會分享一些我的刷題心得，由于博主水平有限，如有錯誤，歡迎指正，如果有更好的解題思路和演算法可以分享給博主哦！一起加油！一起努力！
📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
??堅持和努力一定能換來詩與遠方！
💭參考書籍：📚《劍指offer第1版》，📚《劍指offer第2版》
💬參考在線編程網站：🌐牛客網🌐力扣
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
博主的碼云gitee，平常博主寫的程式代碼都在里面，
??劍指 Offer 03. 陣列中重復的數字??
找出陣列中重復的數字，
在一個長度為 n 的陣列 nums 里的所有數字都在 0～n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字，
💡示例：
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
💡限制：
2 <= n <= 100000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
??解題思路??
根據題意，陣列有n個元素，陣列元素的范圍為0~n-1，如果陣列中沒有重復的元素，對陣列進行排序后對應下標為i的元素為i，但是陣列中是存在重復數字的，所以有些位置對應多個元素，有些位置則沒有元素，
所以我們可以根據將陣列下標與其對應的陣列元素進行比較，如果相等則跳過，比較下一個陣列下標與其對應陣列元素比較，最多遍歷完整個陣列，如果不相等則將該元素與以該元素為下標所對應的陣列元素進行比較，相等就表示找到了一個重復的元素，回傳該元素的值，不相等則將這兩個元素交換，
時間復雜度：最壞遍歷完陣列，時間復雜度為O(N)，
空間復雜度：沒有開辟新空間，空間復雜度O(1)，
編程語言：C語言
在線編程平臺：力扣
int findRepeatNumber(int* nums, int numsSize){
if (nums == NULL || numsSize <=0)
{
return -1;
}
int i = 0;
while(i < numsSize)
{
if (*(nums + i) < 0)
{
return -1;
}
if (*(nums + i) == i)
{
i++;//如果陣列下標與該下標對應的數（記為m）相等，i指向下一位，否則進行比較該數m與陣列下標為m的數是否相等
continue;
}
else
{
int m = *(nums + i);
if (*(nums + i) == *(nums + m))
{
return *(nums + i);//如果相等，則找到重復數字
}
else
{
*(nums + i) = *(nums + m);//如果不相等，將陣列下標為i對應的數（數字m）與下標為m對應的數交換
*(nums + m) = m;
}
}
}
return -1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/294752.html
標籤：其他
下一篇：我用 MATLAB 提取圖片曲線