CODEWITHSUNDEEP
javaarrays
DanSoren
DanSoren

Reputation: 173

A very long(unknown size) int array of positive integers, separated by negatives. How to reverse these positive subarrays linear time?

Suppose we have a stream of int array of positive and negative integers.I want to use negative numbers as separators, and reverse the positive subarrays. for instance [1, 2, 3, 4, -5, 6, 7, 8, -9, ...] becomes [4,3,2,1,-5, 8, 7, 6, -9, ...] I'm trying to come up with a linear (and possibly in place) solution but i can't.

Upvotes: 0

Views: 144

Answers (3)

user3376587
user3376587

Reputation: 134

This works. I just tested it. (short and sweet)

  int[] array = new int[]{1,2,3,4,-5,6,7,8,-9,10,-11,12,13,14,15};
  ArrayList<Integer> positives = new ArrayList<Integer>();
  ArrayList<Integer> preFinalArray = new ArrayList<Integer>();
  for(int i: array){
    if(i>0) positives.add(new Integer(i));
    else{
        for(int j = positives.size()-1; j>=0; j--) preFinalArray.add(positives.get(j));
        preFinalArray.add(new Integer(i));
        positives.clear();
    }
  }
  if(positives.size()>0) for(int i = positives.size()-1; i>=0; i--) preFinalArray.add(new Integer(positives.get(i)));
  int[] newArray = new int[preFinalArray.size()];
  for(int i = 0; i < newArray.length; i++) newArray[i]=preFinalArray.get(i).intValue();
  for(int i: newArray)System.out.println(i);

Upvotes: 1

user5156016
user5156016

Reputation:

Loop into your array while testing for negatif numbers. Creates arrays 0f integer and use Collections.reverse() on the arrays created.

ArrayList<ArrayList<Integer>> lists = ArrayList<ArrayList<Integer>>();
int subCounter=0;
lists.add(new ArrayList<Integer>());

for(int i=0; i originalArray.length; i++){

   (if originalArry[i] < 0){

      lists.add(new ArrayList<Integer>());
      subCounter++;

   }
   else{
        lists.get(subCounter).add(originalArry[i]);
   }
}

int[] newArray = new int[oroginalArray.length];

int counter = 0;
for(ArrayList<Integer> list : lists){

    Collections.reverse(list);
   for(int i=0; i < list.size(); i++){

       newArray[counter] = list.get(i);
       counter++;

   }

   newArray[counter] = originalArray[counter]; // add the separator
   counter++;


}

It may need debugging but the philosophy is there.

Upvotes: 1

Friwi
Friwi

Reputation: 492

I didn't try this code, but it should work:

public int[] convert(int[] c){
   int[] ret = new int[c.length];
   ArrayList<Integer> rev = new ArrayList<>();
   for(int i = 0; i<c.length; i++){
      if(c[i]>=0){
         //If the number is positive, schedule it to be reversed
         ret.add(i);
      }else{
         //If the number is negative, add the array reversed
         //and then the number itself
         int s = rev.size();
         for(int y = 0; y<s; y++){
            ret[i-1-y] = rev.get(y);
         }
         //Recreate the list to clear the scheduled content
         rev = new ArrayList<>();
         ret[i] = c[i];
      }
   }
   //Flush the end of the array
   int s = rev.size();
   for(int y = 0; y<s; y++){
      ret[c.length-1-y] = rev.get(y);
   }
}

Upvotes: 0

Related Questions