Дан массив 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.