-
Notifications
You must be signed in to change notification settings - Fork 1
/
Tar01.cpp
63 lines (59 loc) · 2.1 KB
/
Tar01.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
Alumno: Gerardo Mauricio Gutiérrez Quintana
Matricula: A00815174
Tarea 1 finding the unique char
*/
#include <iostream>
using namespace std;
// Funcion utilizada para encontrar e imprimir el unico caracter
// Recibe como parametros el string donde se buscara el unico caracter
// y la longitud del string donde se buscara el caracter
void binarySearch(string myString, int size){
// Calcula la mitad del string
// A partir de ahi compara con los caracteres que tiene a los lados
// Al calcular la mitad, se tienen dos posibilidades:
// 1) Que al dividir a la mitad el string el string resultante sea par
// 2) Que al dividir a la mitad el string el string resultante sea impar
// Se observa que:
// 1) Cuando se es par, el caracter unico esta hacia donde se encuentre el caracter igual
// al que se encuentra en la mitad
// Ejemplo: aabb c cdde
// abbc c ddee
// 2) Cuando se es impar, el caracter unico esta hacia donde se encuentre el caracter diferente
// al que se encuentra en la mitad
// Ejemplo: aab b ccd
// aab c cdd
// La manera de encontrar el caracter unico sera cuando el caracter que se encuentra en la posicion media
// sea diferente a los que se encuentran a su lado
// Se podria decir que es una especie de busqueda binaria ya que en base a calcular la mitad
// se eliminan otras opciones haciendo mas eficiente la busqueda.
int mid = size / 2, low = mid - 1, high = mid + 1;
if (myString[mid] != myString[low] && myString[mid] != myString[high]){
cout << myString[mid] << endl;
return;
}
else if (mid % 2 == 0){
if (myString[mid] == myString[low]){
myString = myString.erase(mid + 1, mid);
}
else if (myString[mid] == myString[high]){
myString = myString.erase(0, mid + 2);
}
}
else{
if (myString[mid] != myString[low]){
myString = myString.erase(mid, mid + 1);
}
else if (myString[mid] != myString[high]){
myString = myString.erase(0, mid + 1);
}
}
binarySearch(myString, myString.length());
}
int main(){
string palabra;
cout << "Ingrese el string: ";
cin >> palabra;
binarySearch(palabra, palabra.length());
return 0;
}