Дан массив arr [], содержащий n + 1 целых чисел, где каждое целое число находится в диапазоне от 1 до n (включительно). Есть только один повторяющийся элемент, найдите повторяющийся элемент во временной сложности O (n) и пространстве O (1).
Примеры :
Ввод: arr [] = {1, 4, 3, 4, 2}
Выход: 4
Ввод: arr [] = {1, 3, 2, 1}
Выход: 1Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Approach :
Firstly, the constraints of this problem imply that a cycle must exist. Because each number in an array arr[] is between 1 and n, it will necessarily point to an index that exists. Therefore, the list can be traversed infinitely, which implies that there is a cycle. Additionally, because 0 cannot appear as a value in an array arr[], arr[0] cannot be part of the cycle. Therefore, traversing the array in this manner from arr[0] is equivalent to traversing a cyclic linked list. The problem can be solved just like linked list cycle.
Below is the implementation of above approach:
C++
#include <iostream>
using namespace std;
int findDuplicate(int arr[])
{
int slow = arr[0];
int fast = arr[0];
do
{
slow = arr[slow];
fast = arr[arr[fast]];
} while (slow != fast);
int ptr1 = arr[0];
int ptr2 = slow;
while (ptr1 != ptr2)
{
ptr1 = arr[ptr1];
ptr2 = arr[ptr2];
}
return ptr1;
}
int main()
{
int arr[] = { 1, 3, 2, 1 };
cout << findDuplicate(arr) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG
{
public static int findDuplicate(int []arr)
{
int slow = arr[0];
int fast = arr[0];
do
{
slow = arr[slow];
fast = arr[arr[fast]];
} while (slow != fast);
int ptr1 = arr[0];
int ptr2 = slow;
while (ptr1 != ptr2)
{
ptr1 = arr[ptr1];
ptr2 = arr[ptr2];
}
return ptr1;
}
public static void main(String[] args)
{
int []arr = {1, 3, 2, 1};
System.out.println("" +
findDuplicate(arr));
System.exit(0);
}
}
|
Python3
def findDuplicate(arr):
slow = arr[0]
fast = arr[0]
while True:
slow = arr[slow]
fast = arr[arr[fast]]
if slow == fast:
break
ptr1 = arr[0]
ptr2 = slow
while ptr1 != ptr2:
ptr1 = arr[ptr1]
ptr2 = arr[ptr2]
return ptr1
if __name__ == "__main__":
arr = [ 1, 3, 2, 1 ]
print(findDuplicate(arr))
|
C#
using System;
class GFG
{
public static int findDuplicate(int []arr)
{
int slow = arr[0];
int fast = arr[0];
do
{
slow = arr[slow];
fast = arr[arr[fast]];
} while (slow != fast);
int ptr1 = arr[0];
int ptr2 = slow;
while (ptr1 != ptr2)
{
ptr1 = arr[ptr1];
ptr2 = arr[ptr2];
}
return ptr1;
}
public static void Main()
{
int[] arr = {1, 3, 2, 1};
Console.WriteLine("" +
findDuplicate(arr));
}
}
|
PHP
<?php
function findDuplicate(&$arr)
{
$slow = $arr[0];
$fast = $arr[0];
do
{
$slow = $arr[$slow];
$fast = $arr[$arr[$fast]];
} while ($slow != $fast);
$ptr1 = $arr[0];
$ptr2 = $slow;
while ($ptr1 != $ptr2)
{
$ptr1 = $arr[$ptr1];
$ptr2 = $arr[$ptr2];
}
return $ptr1;
}
$arr = array(1, 3, 2, 1);
echo " " . findDuplicate($arr);
?>
|
Javascript
<script>
function findDuplicate(arr)
{
let slow = arr[0];
let fast = arr[0];
do
{
slow = arr[slow];
fast = arr[arr[fast]];
} while (slow != fast);
let ptr1 = arr[0];
let ptr2 = slow;
while (ptr1 != ptr2)
{
ptr1 = arr[ptr1];
ptr2 = arr[ptr2];
}
return ptr1;
}
let arr = [ 1, 3, 2, 1 ];
document.write(findDuplicate(arr) + "<br>");
</script>
|
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.