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); 

    } 
}