for-loop - GO - 递归函数中的 switch 语句

Question

我有一个正在尝试实现的算法，但从技术角度来看，目前我完全不知道如何实现。

我们有一片 5 个 float :

mySlice := [float1, float2, float3, float4, float5]

还有一个 switch 语句:

aFloat := mySlice[index]

switch aFloat {
  case 1:
    {
       //do something 
    }
  case 2:
    {
       //do something 
    }
  case 3:
    {
       //do something 
    }
  case 4:
    {
       //do something 
    }
  case 5:
    {
       //do something 
    }
  default:
    {
       //somehow go back to slice, take the next smallest and run
       //through the switch statement again
    }
}

我想做的事情如下:

1. 确定mySlice ex的最小元素:smallestFloat
2. 通过 switch 语句运行 smallestFloat
3. 如果 smallestFloat 达到默认情况，则从 mySlice 中取下一个最小的 float
4. 再次执行第 2 步。

我已经设法通过 for 循环和第 2 步完成了第一步，但我仍停留在第 3 步和第 4 步。目前我不知道如何重新喂食再次从 mySlice 到 switch 语句的下一个最小 float ...

如果能阐明我的问题，我将不胜感激。

编辑:我认为将我的解决方案应用于上述算法会很好。

1. 创建另一个 slice ，它将是 mySlice 的排序版本
2. 创建一个 map[int]value，其中索引将对应于未排序 slice 中值的位置，但 map 的项目将按照与已排序 slice 相同的顺序插入。

结果:一个值排序映射，其各自的索引对应于原始未排序 slice 的位置

Answer 1

这是一个使用最小优先级队列的实现。原始输入的 float 片没有改变。它可以在 Go playground 上运行

注意:在处理递归函数时，您需要厌倦堆栈溢出。Go 仅在有限的情况下进行尾递归优化。有关这方面的更多信息，引用this answer .

这个特定示例甚至比分摊的 O(log N) 时间还要好，因为它不必在中途调整优先级队列的大小。这保证了 O(log N)。

package main

import (
    "fmt"
)

func main() {
    slice := []float64{2, 1, 13, 4, 22, 0, 5, 7, 3}
    fmt.Printf("Order before: %v\n", slice)

    queue := NewMinPQ(slice)

    for !queue.Empty() {
        doSmallest(queue)
    }

    fmt.Printf("Order after: %v\n", slice)
}

func doSmallest(queue *MinPQ) {
    if queue.Empty() {
        return
    }

    v := queue.Dequeue()

    switch v {
    case 1:
        fmt.Println("Do", v)
    case 2:
        fmt.Println("Do", v)
    case 3:
        fmt.Println("Do", v)
    case 4:
        fmt.Println("Do", v)
    case 5:
        fmt.Println("Do", v)
    default:
        // No hit, do it all again with the next value.
        doSmallest(queue)
    }
}

// MinPQ represents a Minimum priority queue.
// It is implemented as a binary heap.
//
// Values which are enqueued can be dequeued, but will be done
// in the order where the smallest item is returned first.
type MinPQ struct {
    values  []float64 // Original input list -- Order is never changed.
    indices []int     // List of indices into values slice.
    index   int       // Current size of indices list.
}

// NewMinPQ creates a new MinPQ heap for the given input set.
func NewMinPQ(set []float64) *MinPQ {
    m := new(MinPQ)
    m.values = set
    m.indices = make([]int, 1, len(set))

    // Initialize the priority queue.
    // Use the set's indices as values, instead of the floats
    // themselves. As these may not be re-ordered.
    for i := range set {
        m.indices = append(m.indices, i)
        m.index++
        m.swim(m.index)
    }

    return m
}

// Empty returns true if the heap is empty.
func (m *MinPQ) Empty() bool { return m.index == 0 }

// Dequeue removes the smallest item and returns it.
// Returns nil if the heap is empty.
func (m *MinPQ) Dequeue() float64 {
    if m.Empty() {
        return 0
    }

    min := m.indices[1]

    m.indices[1], m.indices[m.index] = m.indices[m.index], m.indices[1]
    m.index--
    m.sink(1)
    m.indices = m.indices[:m.index+1]
    return m.values[min]
}

// greater returns true if element x is greater than element y.
func (m *MinPQ) greater(x, y int) bool {
    return m.values[m.indices[x]] > m.values[m.indices[y]]
}

// sink reorders the tree downwards.
func (m *MinPQ) sink(k int) {
    for 2*k <= m.index {
        j := 2 * k

        if j < m.index && m.greater(j, j+1) {
            j++
        }

        if m.greater(j, k) {
            break
        }

        m.indices[k], m.indices[j] = m.indices[j], m.indices[k]
        k = j
    }
}

// swim reorders the tree upwards.
func (m *MinPQ) swim(k int) {
    for k > 1 && m.greater(k/2, k) {
        m.indices[k], m.indices[k/2] = m.indices[k/2], m.indices[k]
        k /= 2
    }
}