Получение ошибки тайм-аута в проблеме New Year Chaos с использованием scala

Question

У меня есть рабочий скала-код для задачи New Year Chaos в Hackerrank, но я получаю ошибки тайм-аута в некоторых тестовых примерах

https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Пожалуйста, помогите мне с оптимизацией кода ниже:

def minimumBribes(q: Array[Int]){
        val c = q.sorted
        var swap = 0
        var count_swap=0
        import scala.util.control._
        val loop = new Breaks
        var temp = 0
        var flag = true

        loop.breakable
        {
            for (i <- q.length-1 to 0 by -1)

            {   
                    swap = 0
                 if (q(i) != i+1)
                 {
                        swap=i-q.indexOf(i+1)
                        if (swap > 2) {println("Too Chaotic");flag=false;loop.break()}
                        else 
                            {
                                temp= q(q.indexOf(i+1))
                                q(q.indexOf(i+1)) = q(i-1)
                                q(i-1) = q(i)
                                q(i) = temp

                                count_swap += swap
                                if(q.deep == c.deep){
                                loop.break()
                                }
                            }
                }
            }            

        }   
        if (flag)println(count_swap)

    }

Answer 1

Если честно, я не понимаю вашу реализацию, но

1) q.sorted может уже не хватить времени, учитывая, что n равно ~ 10 ^ 5.

2) q.sorted вызов на самом деле избыточен, поскольку это просто последовательность 1..n.

3) использование q.indexOf делает ваш алгоритм O (n ^ 2) сложным.Это можно решить за линейное время.