-1

多数要素（「n」が配列内の要素の数であるn / 2回以上出現する要素）を見つけるためにscalaでsumコードを書きました。機能/ scalaネイティブスタイルのバージョンがどこにあるか知りたいです(これには、"map/"flatmap" などの一致ケースと変換が含まれます。) ループを含む scala コードの以下の命令型スタイルについて。私が使用したコード:

object MajorityElement{

 def printMajority(arr:Array[Int]) ={
 var cand:Int=findCandidate(arr);
  if(isMajority(arr,cand))
    println(cand);
  else
    println("No Majority Element");
 }

def isMajority(arr:Array[Int],Cand:Int):Boolean ={
  var count=0;
   for(i <- 0 until arr.length){
    if(arr(i)== Cand)
      count+=1;
    }
 if (count > arr.size/2)
   return true;
 else false
 }

def findCandidate(arr:Array[Int]):Int ={
 val s = arr.size
 var majIndex:Int = 0;
 var count = 1;
  for(i <- 0 until arr.length){

     if(arr(majIndex) == arr(i))
       count+=1;
     else
       count-=1;
     if(count==0)
       {
       majIndex = i;
       count =1
        }
    }
 return arr(majIndex);
  }
}

任意のシナリオで、命令型スタイルを scala (一致ケースを使用する) で関数型バージョンに記述/変換できるかどうかを教えてください。

4

3 に答える 3

2

最終結果のみに関心がある場合 (そのため必要がない場合isMajority)、それは非常に簡単です。

  def findMajority(xs: List[Int]) = {
    val mostFrequent = xs.groupBy(identity).values.maxBy(_.length)
   if (mostFrequent.length >= xs.length / 2) Some(mostFrequent.head) else None
  } 
  findMajority(List(1, 2, 2, 2, 3, 3, 3, 3, 3, 4))
  //Option[Int] = Some(3)

等しい要素をリスト (Mapによって返されるの値GroupBy) にグループ化します。最長のリストを選択します。その長さがリストの半分を超える場合、それは過半数でありSome(、先頭を返し)ます (どの要素でも構いません。それらはすべて同じ値です)。それ以外の場合は、戻るNone

于 2016-02-11T11:19:16.670 に答える
1

命令的思考から機能的思考への移行には、時間と研究が必要です。1 つのアプローチは、SO でコード例を見つけ、標準ライブラリの助けを借りて、何が起こっているのかを理解するまで分解することです。

ここでは、開始するための簡単な情報を示します。

def isMajority(arr:Array[Int],cand:Int):Boolean =
  arr.count(_ == cand) > arr.size/2
于 2016-02-11T08:12:40.143 に答える
0

Threr は Native Scala Style ではありませんが、コードは Functional Style (値指向) にすることができます

(変数なし、副作用なし、純粋関数)

object MajorityElement {

  case class Candidate(idx: Int, count: Int)

  def solve(arr: Array[Int]): Option[Int] = {
    val candidate = findCandidate(arr)

    if (isMajority(arr, candidate)) Option(arr(candidate.idx))
    else None
  }

  def isMajority(arr: Array[Int], candidate: Candidate) =
    arr.count(_ == arr(candidate.idx)) > arr.size / 2

  def findCandidate(arr: Array[Int]): Candidate =
    arr.indices.foldLeft(Candidate(0, 1)) { (acc, idx) =>
      val newAcc =
        if (arr(acc.idx) == arr(idx)) acc.copy(count = acc.count + 1)
        else acc.copy(count = acc.count - 1)

      if (newAcc.count == 0) Candidate(idx, 1)
      else newAcc
    }
}

val arr = Array(1, 1, 1, 2, 3, 4, 1)
val ret = MajorityElement.solve(arr)

ret match {
  case Some(n) => println(s"Found Majority Element: $n")
  case None => println("No Majority Element")
}
于 2016-02-11T08:16:11.603 に答える