how to get the index of the duplicate pair in the a list using scala-CodePudding

I have a Scala list below :

val numList =  List(1,2,3,4,5,1,2)

I want to get index of the same element pair in the list. The output should look like (0,5),(1,6)

How can I achieve using map?

def catchDuplicates(num : List[Int]) : (Int , Int) = {
  val count = 0;
  val emptyMap: HashMap[Int, Int] = HashMap.empty[Int, Int]
  for (i <- num)
    if (emptyMap.contains(i)) {
      emptyMap.put(i, (emptyMap.get(i))   1)  }
    else {
      emptyMap.put(i, 1)
    }
}

CodePudding user response：

How can I achieve using map?

You can't.
Because you only want to return the indexes of the elements that appear twice; which is a very different kind of transformation than the one that map expects.

You can use foldLeft thought.

object catchDuplicates {
  final case class Result[A](elem: A, firstIdx: Int, secondIdx: Int)
  
  private final case class State[A](seenElements: Map[A, Int], duplicates: List[Result[A]]) {
    def next(elem: A, idx: Int): State[A] =
      seenElements.get(key = elem).fold(
        ifEmpty = this.copy(seenElements = this.seenElements   (elem -> idx))
      ) { firstIdx =>
        State(
          seenElements = this.seenElements.removed(key = elem),
          duplicates = Result(elem, firstIdx, secondIdx = idx) :: this.duplicates
        )
      }
  }
  
  private object State {
    def initial[A]: State[A] =
      State(
        seenElements = Map.empty,
        duplicates = List.empty
      )
  }
  
  def apply[A](data: List[A]): List[Result[A]] =
    data.iterator.zipWithIndex.foldLeft(State.initial[A]) {
      case (acc, (elem, idx)) =>
        acc.next(elem, idx)
    }.duplicates // You may add a reverse here if order is important.
}

Which can be used like this:

val numList =  List(1,2,3,4,5,1,2)
val result = catchDuplicates(numList)
// result: List[Result] = List(Result(2,1,6), Result(1,0,5))

You can see the code running here.

CodePudding user response：

Let's make the challenge a little more interesting.

val numList = List(1,2,3,4,5,1,2,1)

Now the result should be something like (0, 5, 7),(1, 6), which makes it pretty clear that returning one or more tuples is not going to be feasible. Returning a List of List[Int] would make much more sense.

def catchDuplicates(nums: List[Int]): List[List[Int]] =
  nums.zipWithIndex            //List[(Int,Int)]
      .groupMap(_._1)(_._2)    //Map[Int,List[Int]]
      .values                  //Iterable[List[Int]]
      .filter(_.lengthIs > 1)
      .toList                  //List[List[Int]]

CodePudding user response：

I think returning tuple is not a good option instead you should try Map like -

object FindIndexOfDupElement extends App {

  val numList = List(1, 2, 3, 4, 5, 1, 2)

  @tailrec
  def findIndex(elems: List[Int], res: Map[Int, List[Int]] = Map.empty, index: Int = 0): Map[Int, List[Int]] = {
    elems match {
      case head :: rest =>
        if (res.get(head).isEmpty) {
          findIndex(rest, res    Map(head -> (index :: Nil)), index   1)
        } else {
          val updatedMap: Map[Int, List[Int]] = res.map {
            case (key, indexes) if key == head => (key, (indexes :  index))
            case (key, indexes) => (key, indexes)
          }
          findIndex(rest, updatedMap, index   1)
        }
      case _ => res
    }
  }

  println(findIndex(numList).filter(x => x._2.size > 1))

}

you can clearly see the number(key) and respective index in the map - HashMap(1 -> List(0, 5), 2 -> List(1, 6))