retagged by
1,637 views
2 votes
2 votes
Given an array with possible repeating elements you have to rearrange such that elements are alternatively decreasing and increasing (strict increase/decrease). For example, suppose the given array is 1 1 2 3 4 5 one possible answer would be 2 1 3 1 5 4.
Assumption: Solution do exist for any given input.
Hint: Try to avoid sorting.
retagged by

1 Answer

Best answer
2 votes
2 votes

A simple algorithm- iterate over the array and comparing consecutive elements as in bubble sort and swapping if the required condition is violated. 

In case elements are repeated, swap the one with the next distinct number. 

Should run in $O(n)$. 

import java.io.*;
public class Zigzag{

	int findg(Integer[] array, int el, int index){
		int i = index;
		while((i < array.length) && (array[i] == el)) 
			i++;
		if(i < array.length)
			return i;
		i = 0;
		while(array[i] == el)
			i++;
			return i;

	}
	void rearrange(Integer[] array) {
		for(int i = 0; i< array.length-1; i++)
		{
			if(array[i] == array[i+1])
			{
				int ind = findg(array, array[i],  i+2);
				if(array[ind] > array[i])
				{
					array[i%2 == 0? i: i+1] = array[ind];  
					array[ind] = array[i%2 == 0? i+1: i];
				}
				else{
					array[i%2 == 1? i: i+1] = array[ind];  
					array[ind] = array[i%2 == 1? i+1: i];
				} 
			}
			else if(((array[i] < array[i+1]? 1: 0) ^ (i%2)) > 0)
			{
				int tmp = array[i];
				array[i] = array[i+1];
				array[i+1] = tmp;
			}
			 
		}
		
	}
	void printArray(Integer[] array){
		for(int i = 0; i < array.length; i++)
		{
			System.out.print(array[i]+" ");

		}
	}


	public static void main(String args[]) {

		Zigzag myArray = new Zigzag(); //Initialize class
		Integer[] array = new Integer[args.length];
		int i = 0;
		for(String word:args)
			array[i++]=Integer.parseInt(word);
		myArray.rearrange(array);
		myArray.printArray(array);

	}

}
selected by

Related questions

4 votes
4 votes
2 answers
1
im.raj asked May 24, 2016
5,536 views
The information about an array used in program will be stored inSymbol TableActivation RecordBoth (A) and (B)Dope Vector
2 votes
2 votes
2 answers
2
Arjun asked Jul 3, 2016
2,977 views
Given an array of $n$ elements find the maximum continuous sum in it. For example consider the below array of $n=6$.23 4 -10 2 15 1Answer is 35.
1 votes
1 votes
0 answers
3
Arjun asked Jun 6, 2016
449 views
Write an object oriented code for representing boolean expressions and then a function for checking the equivalence of two boolean expressions.
0 votes
0 votes
0 answers
4
Arjun asked Jun 6, 2016
1,053 views
Given an arithmetic expression involving *, + only write an object oriented code for its representation and evaluation