Javaは再帰的に配列内で同じ番号をマージする

Question

配列内で同じ値を乗算してマージする方法を書いてみたい。私は再帰的にそれをやりたい 数字のシーケンスは、それと似た数字がある場合、マージする必要があります。 例えば1,2,5,5,4という数字がある場合は「1 2 25 4」になり、5,5,5,6は「125 6」になります。

誰でも手助けできますか？

Answer 1

このアプローチは、分裂と征服を利用し、O（n log n）で実行する必要があります。

package edu.gwu.seas.cs6212.hw3; 

import java.util.ArrayList; 
import java.util.List; 
import java.util.Map; 
import java.util.Iterator; 
import java.util.Map.Entry; 
import java.util.TreeMap; 

public class Tester { 
    public static void main(String [] args){ 
     System.out.println("Merging 1, 2, 5, 5, 4: "); 
     int [] originalArray = {1, 2, 5, 5, 4}; 
     int [] mergedArray = mergeSequences(originalArray); 
     StringBuilder sb = new StringBuilder(); 
     for(int element : mergedArray){ 
      sb.append(element); 
      sb.append(","); 
     } 
     sb.deleteCharAt(sb.length()-1); //Remove final comma 
     System.out.println(sb.toString()); 
     sb.delete(0, sb.length()); 
     System.out.println("Merging 5, 5, 5, 6: "); 
     int [] originalArray2 = {5, 5, 5, 6}; 
     int [] mergedArray2 = mergeSequences(originalArray2); 
     for(int element : mergedArray2){ 
      sb.append(element); 
      sb.append(","); 
     } 
     sb.deleteCharAt(sb.length()-1); //Remove final comma 
     System.out.println(sb.toString()); 
    } 

    private static int [] mergeSequences(int [] originalArray){ 

     Map<Integer,Integer> indiciesMap = mergeDivideAndConquer(originalArray, 0, originalArray.length -1, new TreeMap<Integer,Integer>()); 
     int indexCounter = 0; 
     List<Integer> mergedList = new ArrayList<Integer>(); 
     Iterator<Entry<Integer, Integer>> it = indiciesMap.entrySet().iterator(); 
     if(it.hasNext()){ 
      while(it.hasNext()){ 
       Entry<Integer,Integer> firstEntry = it.next(); 
       int firstSequenceBeginIndex = firstEntry.getKey(); 
       int firstSequenceEndIndex = firstEntry.getValue(); 
       while(indexCounter < firstSequenceBeginIndex){ 
        mergedList.add(originalArray[indexCounter]); 
        indexCounter++; 
       } 
       //Now we've reached first entry 
       int multiplicativeSum = 1; 
       while(indexCounter <= firstSequenceEndIndex){ 
        multiplicativeSum *= originalArray[indexCounter]; 
        indexCounter++; 
       } 
       mergedList.add(multiplicativeSum); 
      } 
      //Add remaining elements 
      while(indexCounter < originalArray.length){ 
       mergedList.add(originalArray[indexCounter++]); 
      } 

     } else{ 
      for(int element : originalArray){ 
       mergedList.add(element); 
      } 
     } 
     return mergedList.stream().mapToInt(i -> i).toArray(); 
    } 

    private static Map<Integer,Integer> findCrossingArray(final int [] originalArray, final int i, final int midpoint, 
      final int j, Map<Integer,Integer> indiciesMap){ 
     int leftIndexOfSequence = -1; 
     for(int leftCounter = midpoint; leftCounter >= i; leftCounter--){ 
      if(originalArray[leftCounter] == originalArray[midpoint]){ 
       leftIndexOfSequence = leftCounter; 
      } else{ 
       break; 
      } 
     } 
     int rightIndexOfSequence = midpoint; 
     for(int rightCounter = midpoint + 1; rightCounter <= j; rightCounter++){ 
      if(originalArray[rightCounter] == originalArray[midpoint]){ 
       rightIndexOfSequence = rightCounter; 
      } else{ 
       break; 
      } 
     } 
     if(leftIndexOfSequence != -1 && leftIndexOfSequence != rightIndexOfSequence){ 
      indiciesMap.put(leftIndexOfSequence, rightIndexOfSequence); 
     } 
     return indiciesMap; 
    } 

    private static Map<Integer,Integer> mergeDivideAndConquer(final int [] originalArray, final int i, final int j, Map<Integer,Integer> indiciesMap){ 
     //Base case 
     if(j == i){ 
      return indiciesMap; 
     } 
     //Divide recursively into smaller subproblems 
     int midpoint = Math.floorDiv((i + j),2); 
     Map<Integer,Integer> left = mergeDivideAndConquer(originalArray, i, midpoint, indiciesMap); 
     Map<Integer,Integer> right = mergeDivideAndConquer(originalArray, midpoint + 1, j, indiciesMap); 
     //Combine subsolutions 
     return findCrossingArray(originalArray, i, midpoint, j, indiciesMap); 

    } 
}