algorithm - For 循环 vs While 循环 - 荷兰国旗

Question

我正在尝试在golang中使用for循环和while循环来实现荷兰国旗问题。

问题陈述 - 对于给定的数组，以这样一种方式排列元素，即大于枢轴的元素位于枢轴的右侧，小于数组的元素位于数组的左侧。例子 -

输入 - [3 2 4 1 6 3 7 5] ，枢轴 = 4

输出 - [3 2 1 3 4 7 5 6]

For循环实现[不按预期工作]

package main

import (
    "fmt"
)

func main() {
    in := []int{3, 2, 4, 1, 6, 3, 7, 5}
    pivot := 4
    run(in, pivot)

}

func run(in []int, pivot int) {

    fmt.Println("before : ", in)

    lBoundary := 0

    hBoundary := len(in) - 1

    for i := 0; i <= hBoundary; i++ {
        if in[i] > pivot {
            in[i], in[hBoundary] = in[hBoundary], in[i]
            hBoundary--
        } else if in[i] < pivot {
            in[i], in[lBoundary] = in[lBoundary], in[i]
            lBoundary++
        }
    }

    fmt.Println("after: ", in)

}

While 循环实现 [按预期工作] -

    package main

import (
    "fmt"
)

func main() {
    in := []int{3, 2, 4, 1, 6, 3, 7, 5}
    pivot := 4
    run(in, pivot)

}

func run(in []int, pivot int) {

    fmt.Println("before : ", in)

    i := 0
    lBoundary := 0

    hBoundary := len(in) - 1

    for i <= hBoundary {
        if in[i] > pivot {
            in[i], in[hBoundary] = in[hBoundary], in[i]
            hBoundary--
        } else if in[i] < pivot {
            in[i], in[lBoundary] = in[lBoundary], in[i]
            lBoundary++
            i++
        } else {
            i++
        }
    }
    fmt.Println("after: ", in)
}

我无法确定 for 循环实现中的问题。

标签： algorithmloopsfor-loopgowhile-loop

Answer 1

i问题是，如果您仅针对两个条件更新 while 循环计数器，即

    else if in[i] < pivot {
        in[i], in[lBoundary] = in[lBoundary], in[i]
        lBoundary++
        i++
    } else {
        i++
    }

但是在 for 循环的情况下，每次执行循环时计数器都会增加，因为i++.

因此，如果您更新 for 循环代码以将增量条件放在循环内，它将按预期运行：

package main

import (
    "fmt"
)

func main() {
    in := []int{3, 2, 4, 1, 6, 3, 7, 5}
    pivot := 4
    run(in, pivot)

}

func run(in []int, pivot int) {

    fmt.Println("before : ", in)

    lBoundary := 0

    hBoundary := len(in) - 1
    // remove i++ condition
    for i := 0; i <= hBoundary; {
        if in[i] > pivot {
            in[i], in[hBoundary] = in[hBoundary], in[i]
            hBoundary--  // no increment in this condition
        } else if in[i] < pivot {
            in[i], in[lBoundary] = in[lBoundary], in[i]
            lBoundary++
            i++  // add the increment condition here
        } else {
            i++ // and here as well
        }

    }

    fmt.Println("after: ", in)

}