Trova due linee orizzontali per minimizzare la distanza dai punti sparsi

0

Ho problemi con una domanda di codifica che ho trovato utile per un'intervista:

Un grafico a dispersione di punti su una pagina, disegna due linee orizzontali (queste linee sono parallele) attraverso la pagina in modo tale che la distanza perpendicolare y di una linea da tutti i punti sia minimizzata. Conta la distanza totale da ciascun punto alla linea più vicina (conta solo la distanza da ciascun punto alla linea più vicina, ignora la distanza più lunga, quando la distanza è la stessa, scegli uno dei due). Descrivi un algoritmo per trovare queste due linee.

Il mio approccio:

Ho preso in considerazione la forzatura bruta di questo controllando tutte le possibilità in intervalli di 1 a partire dall'asse y più alto che termina con l'asse y più basso dei punti, ma forse non è il modo migliore. Ho anche considerato di dividere i punti in due gruppi in base all'asse y, tuttavia ci sono alcuni casi limite che falliranno.

Qualcuno sa un modo più efficiente per farlo?

    
posta Hyperion 27.11.2018 - 00:36
fonte

1 risposta

1

Sì, c'è un modo molto più efficace per farlo. Off the cuff posso scrivere un algoritmo O (N log (N)). Poiché questa è una domanda di prova, il punto non è risolverlo, è il processo di risoluzione.

Il problema che sembri avere è un problema di prospettiva. Prova a ridurre le dimensioni del problema.

  • Come risolverebbe questo per due punti?
  • Come risolverebbe questo per tre punti? quattro punti? cinque punti?
  • Dato che hai già risolto questo problema per i punti K, puoi risolverlo per i punti K + 1?
  • Quel punto K + 1 deve avere determinate proprietà?
  • La ricezione dei punti in un ordine particolare la rende più facile da risolvere?
  • Considererebbe i punti uno, due, tre alla volta che lo rendono più facile da risolvere?
  • Come si comporta ogni linea come punto viene aggiunto?
  • Puoi approfittare di questo comportamento?

A questo punto probabilmente avrai capito se e come ordinare i punti, come vengono selezionati e quanti punti prenderai in una volta. Saprai come aggiornare la soluzione per il prossimo punto e saprai che la tua risposta è corretta dopo aver considerato tutti i punti.

    
risposta data 27.11.2018 - 02:47
fonte

Leggi altre domande sui tag