naivecoderr
BAN USERThere are 3 options to do this :
1) Scan array 1 char at a time and compare with remaining chars. If no duplicate found return, you have just found the first non-repeated char. Time complexity : o(n*n)
2) Sort the array. Scan array by comparing adjacent element. If you find element which is different than its adjacent element, return it. Time complexity : o(n log n) + o(n)
3) Use a hashMap of character and its count. Scan array to populate this map. Finally Scan array and check the count on each char from this hashMap. If it is 1, return that element. Time complexity : o(n) but needs additional o(n) space for hash map.
Algorithm:
1)First scan both arrays to create a hashmap to hold values of id and weight. This will allow us to get final weight of every id. ~o(n) time
2) Now create a new array that is equal to size of this hashmap. Construct this array from the elements of hashmap
3) Finally compare array elements based on weight to get final result. (o(n lg n))
4) Total time complexity is o(n)+ o(n lg n) and ~o(n) space
public class ObjectSort {
public static void main(String[] args) {
Item[] arr1 = new Item[3];
//first create some items for first array
Item i1 = new Item(1,10);
Item i2 = new Item(2,20);
Item i3 = new Item(3,30);
arr1[0] = i1;
arr1[1] = i2;
arr1[2] = i3;
//create items for second array
Item[] arr2 = new Item[3];
Item i11 = new Item(2,10);
Item i12 = new Item(3,20);
Item i13 = new Item(4,30);
arr2[0] = i11;
arr2[1] = i12;
arr2[2] = i13;
Item[] sortedArray = sortObjectArrays(arr1,arr2);
for(int i = 0 ; i<sortedArray.length;i++){
System.out.println("Id:"+sortedArray[i].id+" and weight:"+sortedArray[i].weight);
}
}
private static Item[] sortObjectArrays(Item[] arr1, Item[] arr2) {
// step 1: create an hashmap with id to weight values :o(n)
HashMap<Integer,Integer> IdToWeightMap = getIdToWeightMap(arr1, arr2);
//step 2: Now, we have all the ids have their final weight, we will create array from hashMap
Item[] arr = new Item[IdToWeightMap.size()];
int count = 0;
//create array from map
for(Integer i : IdToWeightMap.keySet()){
arr[count] = new Item(i,IdToWeightMap.get(i));
count++;
}
//sort this array based on weights and return
//uses lambda expression to compare 2objects.
Arrays.sort(arr,(a,b)->((Integer)a.weight).compareTo((Integer)b.weight));
return arr;
}
public static HashMap<Integer,Integer> getIdToWeightMap(Item[] arr1, Item[] arr2){
HashMap<Integer,Integer> IdToWeightMap = new HashMap<>();
//scan first array
for(int i = 0 ; i<arr1.length;i++){
if(IdToWeightMap.containsKey(arr1[i].id)){
IdToWeightMap.put(arr1[i].id,IdToWeightMap.get(arr1[i].id)+arr1[i].weight);
}else{
IdToWeightMap.put(arr1[i].id, arr1[i].weight);
}
}
//scan second array
for(int i = 0 ; i<arr2.length;i++){
if(IdToWeightMap.containsKey(arr2[i].id)){
IdToWeightMap.put(arr2[i].id,IdToWeightMap.get(arr2[i].id)+arr2[i].weight);
}else{
IdToWeightMap.put(arr2[i].id, arr2[i].weight);
}
}
return IdToWeightMap;
}
public static class Item{
public int id;
public int weight;
public Item(int id,int weight){
this.id = id;
this.weight = weight;
}
}
}
A simple non recursive version:
- naivecoderr August 15, 2016