Переместить нули в конец массива

Question

Я пытаюсь решить проблему ниже в scala

Input:[1,0,44,55,0,43,78,99]
output:[1,44,55,43,78,99,0,0]

вот что я пробовал

def moveZeros(nums:Array[Int]): Array[Int] ={
    for(i<-0 until nums.length ; j<-0 until nums.length){
      if(nums(j)!=0)
      {
        var temp:Int = nums(i)
        nums(i)=nums(j)
        nums(j)=temp
      }

    }
    nums
  }

вывод: [0,0,1,44,55, 78,99,43]

не ожидаемый результат

Я ищу временную сложность o (n) и решение пространственной сложности O (1)

Это проблема leetcode https://leetcode.com/problems/move-zeroes/

Answer 1

• 1000

Answer 2

Вы можете попробовать что-то вроде этого:

nums.zipWithIndex
   .sortBy(t => if (t._1 == 0) Int.MaxValue else t._2)
   .map(_._1)

zipWithIndex отобразит вашу коллекцию в последовательность кортежей значения элемента и его индекса (например, [(1, 0), (0, 21), (44, 2)] для начала ваш примерный массив)

sortBy выполнит упорядочение либо по индексу элемента, либо Int.MaxValue

map вернет карту к исходному элементу.

Answer 3

Это чистое решение FP с временной сложностью O (n) и пространственной сложностью O (1). поместится в памяти:

object MoveZeros extends App {
  def moveZerosToEnd(input: Iterator[Int]): Iterator[Int] = {
    val endOfInputSignal = None
    val iteratorWithEndSignal: Iterator[Option[Int]] =
      input.map(Some(_)) ++ Iterator.single(endOfInputSignal)
    iteratorWithEndSignal.scanLeft((0, Iterator.empty[Int])) {
      case ((zerosCounter, _), value) => value match {
        case Some(value) =>
          if (value == 0)
            // Count zero and drop it
            (zerosCounter + 1, Iterator.empty)
          else
            (zerosCounter, Iterator.single(value))
        case None =>
          // Add counted zeros to the end
          (zerosCounter, Iterator.fill(zerosCounter)(0))
      }
    }.flatMap(_._2)
  }
  val input = List(1,0,44,55,0,43,78,99)
  val expected = List(1,44,55,43,78,99,0,0)
  val res = moveZerosToEnd(input.iterator)
    .toList // To list only for easy testing
  assert(res == expected)
  println(res)
}

Answer 4

Вы можете найти все неизменные, функциональные, «истинные Scala» способы сделать это в приведенных выше ответах. Но, учитывая сложность времени O (N) и сложность пространства O (1), ничто не сравнится с изменяемым, эффективным алгоритмом на месте!

Вот реализация с массивом Scala с использованием foldLeft:

val arr = Array(1, 0, 44, 55, 0, 43, 78, 99)
val lastNonZero = arr.foldLeft(0) { 
  (zeros, elem) => if (elem != 0) { arr(zeros) = elem; zeros+1 } else zeros
}

(lastNonZero until arr.length).foreach{ i => arr(i) = 0 }

Нет лишнего места из-за создания коллекции (даже .toList / .toArray) и без сортировки.

введите описание изображения здесь

Answer 5

Функциональное и неизменное решение, также очень простое для понимания:

def moveZerosToEnd(input: Seq[Int]): Seq[Int] = {
    val ZERO = 0
    val zeroCount = input.count(_==ZERO)
    val removeZeros = input.filter(_!=ZERO)
    val zeroSuffix = Seq.fill(zeroCount)(ZERO)
    removeZeros ++ zeroSuffix
}  

введите описание изображения здесь

Временная сложность: O(n): фиксированное количество итераций в последовательности. Сложность пространства: O(n): removeZeros, zeroSuffix, а строка вывода может занимать до n места, поэтому сложность составляет O(n).