JustDifferent
BAN USERDid a solution in golang see comment for explanation:
package main
import (
"fmt"
"math"
)
func main() {
arr := []Point{Point{X: 3, Y: 40}, Point{X: 19, Y: 4}, Point{X: 7, Y: 4}, Point{X: 1, Y: 4}, Point{X: 17, Y: 4}, Point{X: 11, Y: 4}}
fmt.Println(Closest(arr, 2))
}
type Point struct {
X int
Y int
}
func (point Point) distance() float64 {
a := math.Pow(float64(point.X), 2)
b := math.Pow(float64(point.Y), 2)
return math.Sqrt(a + b)
}
func Closest(points []Point, k int) []Point {
position := selection(points, k)
//return slice of k closest points
return points[0:position]
}
//Quick Selection algorithm
//Basically what amounts to a partial insertion sort
//Customized for Point struct
//Return position kth Point
func selection(arr []Point, k int) int {
to := len(arr) - 1
for from := 0; from < to; {
read := from
write := to
midV := arr[(read+write)/2].distance()
for read < write {
if arr[read].distance() >= midV {
swap(arr, read, write)
write = write - 1
} else {
read = read + 1
}
}
if arr[read].distance() > midV {
read = read - 1
}
if k <= read {
to = read
} else {
from = read + 1
}
}
return k
}
func swap(arr []Point, i int, j int) {
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}
Solution done in golang. Converts each word to an array of character counts in one pass. O(n).
This array is the key, the word list is the value.
So O(n+m) where n is the word length and m is the number of words. Also uses stores a 256 length byte array for each anagram (regardless of length of each word and frequency of each anagram)
Sorting at best is O(n log n) so be careful of sorting based solutions. Also since strings are usually immutable across most languages be careful of solutions that use string split and string append as they add (and hide) complexity.
- JustDifferent January 18, 2014