algorithm - rectas - tipos de lineas mixtas

Puzzle: Encuentra el orden de n personas paradas en una línea(según su altura)

Question

Vi esta pregunta en Careercup.com:

Dadas las alturas de n personas paradas en una línea y una lista de números correspondiente a cada persona (p) que da el número de personas que son más altas que p y están de pie frente a p. Por ejemplo,

Alturas: 5 3 2 6 1 4

InFronts: 0 1 2 0 3 2

Significa que el orden real real es: 5 3 2 1 6 4

La pregunta obtiene las dos listas de Alturas e Intros, y debe generar el orden en línea.

Mi solución:

Podría resolverse ordenando primero la lista en orden descendente. Obviamente, para ordenar, necesitamos definir un objeto Persona (con dos atributos de Altura e InFront) y luego ordenar Personas en función de su altura. Luego, utilizaría dos pilas, una pila principal y una pila templada, para construir el orden.

Comenzando por el más alto, colócalo en la pila principal. Si la siguiente persona tiene un valor InFront mayor que la persona en la parte superior de la pila, eso significa que la nueva persona debe agregarse antes que la persona en la parte superior. Por lo tanto, necesitamos sacar personas de la pila principal, insertar la nueva persona y luego devolver a las personas que aparecieron en el primer paso. Yo usaría una pila de temperatura para mantener el orden de las personas reventadas. Pero, ¿cuántos deberían aparecer? Como la lista está ordenada, necesitamos mostrar exactamente el número de personas frente a la nueva persona, es decir, InFront correspondiente.

Creo que esta solución funciona Pero el peor orden de casos sería O (n ^ 2): al colocar a una persona en su lugar, es necesario que salte todos los anteriores.

¿Hay alguna otra solución? posiblemente en O (n)?

Answer 1

Creo que un enfoque puede ser el siguiente. Aunque nuevamente parece ser O (n ^ 2) en el presente.

Clasifique la matriz de altura y la correspondiente matriz ''p'' en orden ascendente de alturas (en O (nlogn)). Elige el primer elemento en la lista. Coloque ese elemento en la matriz final en la posición dada por el índice p.

Por ejemplo después de ordenar,
H - 1, 2, 3, 4, 5, 6
p - 3, 2, 1, 2, 0, 0.

El primer elemento debe ir en posición 3. Por lo tanto, la matriz final se convierte en:
--- 1--

2. ° elemento irá en posición 2. Por lo tanto, la matriz final se convierte en:
--21--

El tercer elemento debe ir en la posición 1. Por lo tanto, la matriz final se convierte en:
-321--

El cuarto elemento irá en la posición 2. Esta es la posición entre los vacíos. Por lo tanto la matriz final se convierte en:
-321-4

El quinto elemento irá en la posición 0. Por lo tanto, la matriz final se convierte en:
5321-4

El 6 ° elemento debería ir en la posición 0. Por lo tanto, la matriz final se convierte en:
532164

Answer 2

El algoritmo O (nlogn) es posible.

Primero asuma que todas las alturas son diferentes.

Clasifica a las personas por alturas. Luego itera del más corto al más alto. En cada paso necesita una forma eficiente de colocar a la siguiente persona en la posición correcta. Tenga en cuenta que las personas que ya hemos colocado no son más altas que la persona actual. Y las personas que colocamos después son más altas que la actual. Entonces, tenemos que encontrar un lugar tal que la cantidad de posiciones vacías en el frente sea igual al valor inicial de esta persona. Esta tarea puede realizarse usando una estructura de datos llamada árbol de intervalos en el tiempo O (logn). Entonces, el tiempo total de un algoritmo es O (nlogn).

Este algoritmo funciona bien en caso de que no haya vínculos. Como se puede suponer con seguridad que los lugares vacíos hasta el frente serán ocupados por personas más altas.

En caso de que los lazos sean posibles, debemos asegurarnos de que las personas de la misma altura se coloquen en un orden creciente de sus posiciones. Se puede lograr si procesaremos personas por valor de frentes no decrecientes. Por lo tanto, en caso de posibles vínculos, también deberíamos considerar los valores de Fronteras al ordenar personas.

Y si en algún momento no podemos encontrar una posición para la siguiente persona, entonces la respuesta es "es imposible satisfacer las limitaciones del problema".

Answer 3

Estoy usando LinkedList para esto. Clasifique tallCount [] en orden ascendente y, en consecuencia, vuelva a colocar los elementos en alturas []. Esto también es capaz de manejar los elementos duplicados.

public class FindHeightOrder {
public int[] findOrder(final int[] heights, final int[] tallCount) {
if (heights == null || heights.length == 0 || tallCount == null
|| tallCount.length == 0 || tallCount.length != heights.length) {
return null;
}
LinkedList list = new LinkedList();
list.insertAtStart(heights[0]);
for (int i = 1; i < heights.length; i++) {
if (tallCount[i] == 0) {
Link temp = list.getHead();
while (temp != null && temp.getData() <= heights[i]) {
temp = temp.getLink();
}
if (temp != null) {
if (temp.getData() <= heights[i]) {
list.insertAfterElement(temp.getData(), heights[i]);
} else {
list.insertAtStart(heights[i]);
}
} else {
list.insertAtEnd(heights[i]);
}
} else {
Link temp = list.getHead();
int pos = tallCount[i];
while (temp != null
&& (temp.getData() <= heights[i] || pos-- > 0)) {
temp = temp.getLink();
}
if (temp != null) {
if (temp.getData() <= heights[i]) {
list.insertAfterElement(temp.getData(), heights[i]);
} else {
list.insertBeforeElement(temp.getData(), heights[i]);
}
} else {
list.insertAtEnd(heights[i]);
}
}
}
Link fin = list.getHead();
int i = 0;
while (fin != null) {
heights[i++] = fin.getData();
fin = fin.getLink();
}
return heights;
}
public class Link {
private int data;
private Link link;
public Link(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Link getLink() {
return link;
}
public void setLink(Link link) {
this.link = link;
}
@Override
public String toString() {
return this.data + " -> "
+ (this.link != null ? this.link : "null");
}
}
public class LinkedList {
private Link head;
public Link getHead() {
return head;
}
public void insertAtStart(int data) {
if (head == null) {
head = new Link(data);
head.setLink(null);
} else {
Link link = new Link(data);
link.setLink(head);
head = link;
}
}
public void insertAtEnd(int data) {
if (head != null) {
Link temp = head;
while (temp != null && temp.getLink() != null) {
temp = temp.getLink();
}
temp.setLink(new Link(data));
} else {
head = new Link(data);
}
}
public void insertAfterElement(int after, int data) {
if (head != null) {
Link temp = head;
while (temp != null) {
if (temp.getData() == after) {
Link link = new Link(data);
link.setLink(temp.getLink());
temp.setLink(link);
break;
} else {
temp = temp.getLink();
}
}
}
}
public void insertBeforeElement(int before, int data) {
if (head != null) {
Link current = head;
Link previous = null;
Link ins = new Link(data);
while (current != null) {
if (current.getData() == before) {
ins.setLink(current);
break;
} else {
previous = current;
current = current.getLink();
if (current != null && current.getData() == before) {
previous.setLink(ins);
ins.setLink(current);
break;
}
}
}
}
}
@Override
public String toString() {
return "LinkedList [head=" + this.head + "]";
}
}

}

Answer 4

Existe un algoritmo con complejidad media O (nlogn), sin embargo, la complejidad del peor caso sigue siendo O (n²).

Para lograr esto, puede usar una variación de un árbol binario. La idea es que en este árbol, cada nodo corresponde a una persona y cada nodo realiza un seguimiento de cuántas personas hay delante de él (que es el tamaño del subárbol izquierdo) a medida que se insertan los nodos.

Comience a iterar la matriz de personas en orden decreciente de altura e inserte a cada persona en el árbol comenzando desde la raíz. La inserción es la siguiente:

1. Compare el frontCount de la persona con el valor actual del nodo (raíz al principio).
2. Si es más pequeño, inserte el nodo a la izquierda con el valor 1. Aumente el valor del nodo actual en 1.
3. De lo contrario, desciende a la derecha disminuyendo el frontCount la persona por el valor del nodo actual. Esto permite que el nodo se coloque en la ubicación correcta.

Después de que todos los nodos hayan terminado, un recorrido de inorder da el orden correcto de personas.

Deje que el código hable por sí mismo:

public static void arrange(int[] heights, int[] frontCounts) {
Person[] persons = new Person[heights.length];
for (int i = 0; i < persons.length; i++)
persons[i] = new Person(heights[i], frontCounts[i]);
Arrays.sort(persons, (p1, p2) -> {
return Integer.compare(p2.height, p1.height);
});
Node root = new Node(persons[0]);
for (int i = 1; i < persons.length; i++) {
insert(root, persons[i]);
}
inOrderPrint(root);
}
private static void insert(Node root, Person p) {
insert(root, p, p.frontCount);
}
private static void insert(Node root, Person p, int value) {
if (value < root.value) { // should insert to the left
if (root.left == null) {
root.left = new Node(p);
} else {
insert(root.left, p, value);
}
root.value++; // Increase the current node value while descending left!
} else { // insert to the right
if (root.right == null) {
root.right = new Node(p);
} else {
insert(root.right, p, value - root.value);
}
}
}
private static void inOrderPrint(Node root) {
if (root == null)
return;
inOrderPrint(root.left);
System.out.print(root.person.height);
inOrderPrint(root.right);
}
private static class Node {
Node left, right;
int value;
public final Person person;
public Node(Person person) {
this.value = 1;
this.person = person;
}
}
private static class Person {
public final int height;
public final int frontCount;
Person(int height, int frontCount) {
this.height = height;
this.frontCount = frontCount;
}
}
public static void main(String[] args) {
int[] heights = {5, 3, 2, 6, 1, 4};
int[] frontCounts = {0, 1, 2, 0, 3, 2};
arrange(heights, frontCounts);
}

Answer 5

Como las personas ya corrigieron por entrada original:

Heights : A[] = { 5 3 2 6 1 4 }
InFronts: B[] = { 0 1 2 0 3 2 }
Output should look like: X[] = { 5 3 1 6 2 4 }

Aquí está la forma O (N * logN) de acercarse a la solución (con la suposición de que no hay vínculos).

1. Iteramos sobre la matriz B y construimos la cadena de desigualdades (colocando elementos en un lugar correcto en cada iteración, aquí podemos usar hashtable para O (1) búsquedas):
   • b0> b1
   • b0> b1> b2
   • b3> b0> b1> b2
   • b3> b0> b1> b4> b2
   • b3> b0> b5> b1> b4> b2
2. Ordenar la matriz A y revertirla
3. Inicialice la matriz de salida X, repita la cadena a partir de la n. ° 1 y llene la matriz X colocando los elementos de A en una posición definida en una cadena.

Los pasos # 1 y # 3 son O (N), el paso # 2 es el O más caro (N * logN). Y, obviamente, no es necesario invertir el conjunto ordenado A (en el paso n.º 2).

Answer 6

Esta es la implementación de la idea proporcionada por user1990169. La complejidad es O (N ^ 2).

public class Solution {
class Person implements Comparator<Person>{
int height;
int infront;
public Person(){
}
public Person(int height, int infront){
this.height = height;
this.infront = infront;
}
public int compare(Person p1, Person p2){
return p1.height - p2.height;
}
}
public ArrayList<Integer> order(ArrayList<Integer> heights, ArrayList<Integer> infronts) {
int n = heights.size();
Person[] people = new Person[n];
for(int i = 0; i < n; i++){
people[i] = new Person(heights.get(i), infronts.get(i));
}
Arrays.sort(people, new Person());
Person[] rst = new Person[n];
for(Person p : people){
int count = 0;
for(int i = 0; i < n ; i++){
if(count == p.infront){
while(rst[i] != null && i < n - 1){
i++;
}
rst[i] = p;
break;
}
if(rst[i] == null) count++;
}
}
ArrayList<Integer> heightrst = new ArrayList<Integer>();
for(int i = 0; i < n; i++){
heightrst.add(rst[i].height);
}
return heightrst;
}
}

Answer 7

Estaba resolviendo este problema hoy, esto es lo que se me ocurrió:

La idea es ordenar la matriz de alturas en orden descendente. Una vez, tenemos este conjunto ordenado: seleccione un elemento de este elemento y colóquelo en el conjunto resultante en el índice correspondiente (estoy usando un ArrayList para el mismo, sería bueno usar LinkedList):

public class Solution {
public ArrayList<Integer> order(ArrayList<Integer> heights, ArrayList<Integer> infronts) {
Person[] persons = new Person[heights.size()];
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < persons.length; i++) {
persons[i] = new Person(heights.get(i), infronts.get(i));
}
Arrays.sort(persons, (p1, p2) -> {
return Integer.compare(p2.height, p1.height);
});
for (int i = 0; i < persons.length; i++) {
//System.out.println("adding "+persons[i].height+" "+persons[i].count);
res.add(persons[i].count, persons[i].height);
}
return res;
}
private static class Person {
public final int height;
public final int count;
public Person(int h, int c) {
height = h;
count = c;
}
}
}

Answer 8

Creo que el enfoque indicado arriba es correcto. Sin embargo, falta una pieza crítica en las soluciones anteriores.
Infrontas es el número de candidato más alto antes que la persona actual. Entonces, después de clasificar a las personas según la altura (Ascendente), al ubicar a la persona 3 con enfrente = 2, si la persona 1 y 2 estaban en frente colocados en 0, 1 posición respectivamente, necesita descartar su posición y colocar 3 en la posición 4, Los candidatos IE 2 más altos tomarán posición 2,3.

Como algún árbol de intervalo indicado es la estructura correcta. Sin embargo, un contenedor de tamaño dinámico, con la posición disponible hará el trabajo. (Código a continuación)

struct Person{
int h, ct;
Person(int ht, int c){
h = ht;
ct = c;
}
};
struct comp{
bool operator()(const Person& lhs, const Person& rhs){
return (lhs.h < rhs.h);
}
};
vector<int> heightOrder(vector<int> &heights, vector<int> &infronts) {
if(heights.size() != infronts.size()){
return {};
}
vector<int> result(infronts.size(), -1);
vector<Person> persons;
vector<int> countSet;
for(int i= 0; i< heights.size(); i++){
persons.emplace_back(Person(heights[i], infronts[i]));
countSet.emplace_back(i);
}
sort(persons.begin(), persons.end(), comp());
for(size_t i=0; i<persons.size(); i++){
Person p = persons[i];
if(countSet.size() > p.ct){
int curr = countSet[p.ct];
//cout << "the index to place height=" << p.h << " , is at pos=" << curr << endl;
result[curr] = p.h;
countSet.erase(countSet.begin() + p.ct);
}
}
return result;
}

Answer 9

Encontré este tipo de problema en SPOJ . Creé un árbol binario con poca variación. Cuando se inserta una nueva altura, si el frente es más pequeño que el frente de la raíz, entonces va hacia la izquierda, si no, hacia la derecha.

Aquí está la implementación de C ++:

#include<bits/stdc++.h>
using namespace std;
struct TreeNode1
{
int val;
int _front;
TreeNode1* left;
TreeNode1*right;
};
TreeNode1* Add(int x, int v)
{
TreeNode1* p= (TreeNode1*) malloc(sizeof(TreeNode1));
p->left=NULL;
p->right=NULL;
p->val=x;
p->_front=v;
return p;
}
TreeNode1* _insert(TreeNode1* root, int x, int _front)
{
if(root==NULL) return Add(x,_front);
if(root->_front >=_front)
{
root->left=_insert(root->left,x,_front);
root->_front+=1;
}
else
{
root->right=_insert(root->right,x,_front-root->_front);
}
return root;
}
bool comp(pair<int,int> a, pair<int,int> b)
{
return a.first>b.first;
}
void in_order(TreeNode1 * root, vector<int>&v)
{
if(root==NULL) return ;
in_order(root->left,v);
v.push_back(root->val);
in_order(root->right,v);
}
vector<int>soln(vector<int>h, vector<int>in )
{
vector<pair<int , int> >vc;
for(int i=0;i<h.size();i++) vc.push_back( make_pair( h[i],in[i] ) );
sort(vc.begin(),vc.end(),comp);
TreeNode1* root=NULL;
for(int i=0;i<vc.size();i++)
root=_insert(root,vc[i].first,vc[i].second);
vector<int>v;
in_order(root,v);
return v;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
vector<int>h;
vector<int>in;
for(int i=0;i<n;i++) {int x;
cin>>x;
h.push_back(x);}
for(int i=0;i<n;i++) {int x; cin>>x;
in.push_back(x);}
vector<int>v=soln(h,in);
for(int i=0;i<n-1;i++) cout<<v[i]<<" ";
cout<<v[n-1]<<endl;
h.clear();
in.clear();
}
}