Click here to Skip to main content
15,559,275 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
So I'm trying to sort an vector <string> carInventory based on the order of a vector with 3 elements titled vector <string> promotionOrder.

Ex)

Input:
vector<string> carInventory {"mz", "my", "my", "mx", "mz", "mx", "my", "mz"}
vector<string> promotionOrder {"mz", "mx", "my"}

Output:
{"mz", "mz", "mz", "mx", "mx", "my", "my", "my"} //new carInventory

Here's the function:
vector<string> SortCar::sortCarInventory(vector<string> carInventory, 
vector<string> promotionOrder)

What I have tried:

Currently stuck thinking of a solution with a time complexity of O(N) and <pre>with constant auxiliary space complexity O(1)
Posted
Updated 9-Oct-22 20:09pm
Comments
CPallini 8-Jun-22 4:38am    
I don't know any sorting algorithm warranting O(N).
Richard MacCutchan 8-Jun-22 4:43am    
You cannot use a sort as the sort order is not fixed. You just need to iterate the promotionOrder list and find all the relevant car entries for each one.

Richard has given you a solution of time complexity O(N*M), and auxillary space O(1), where M is the number of entries in the promotionOrder list.

This could be reduced to O(N) with auxiliary space O(M) if we create a hash map where the key is the value of the promotionOrder entry and the mapped value is the position in the promotionOrder table. A set of M counters is initialized to zeroes.

For each carInventory entry:
Look up the position in the hash map
Increment the number of cars in that position.

For all counters:
Insert (counter) entries of the appropriate type into the output.

Reducing the auxiliary space to O(1) is left as an exercise...
 
Share this answer
 
Simple. STL will sort it for you.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900