Authors:
Stuart Reges, Marty Stepp
Chapter:
Java Collections Framework
Exercise:
Exercises
Question:4 | ISBN:9780136091813 | Edition: 2
Question
Write a method called partition that accepts a list of integers and an integer value E as its parameter, and rearrangesc(partitions) the list so that all the elements with values less than E occur before all elements with values greater than E.The exact order of the elements is unimportant, so long as all elements less than E appear before all elements greater than E. For example, for the linked list (15, 1, 6, 12, –3, 4, 8, 21, 2, 30, –1, 9), one acceptable ordering of the list after a call of partition(list, 5) would be (–1, 1, 2, 4, –3, 12, 8, 21, 6, 30, 15, 9). You
may assume that the list contains no duplicates and does not contain the element value E.
Answer
package collections;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
public class Partition {
public static List<Integer> partition(List<Integer> list, int n) {
// crete two lists. one to store elements less then n
// and other to store elements greater than n
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
// store the elements which are less than n in one list1 and other in list2
for (int i = 0; i < list.size(); i++) {
if (list.get(i) < n)
list1.add(list.get(i));
if (list.get(i) > n)
list2.add(list.get(i));
}
// now merge the two lists
list1.addAll(list2);
return list1;
}
public static void main(String args[]) {
List<Integer> list = new ArrayList<>();
Collections.addAll(list, 15, 1, 6, 12, 12, -3, 4, 8, 21, 2, 30, -1, 9);
LinkedHashSet<Integer> LSet = new LinkedHashSet<Integer>(Partition.partition(list, 8));
System.out.println(Arrays.toString(LSet.toArray()));
}
}
Output:
[1, 6, -3, 4, 2, -1, 15, 12, 21, 30, 9]