I'm looking for a solution for this problem.

I have an array which defines the rule of the order of elements like below.

let rule = [A,B,C,D,E,F,G,H,I,J,K]

I then have another array whose element can be removed or added back. So for example, I have a list like this:

var list = [A,D,E,I,J,K]

Now If I want to add element 'B' to 'list' the list should be

var list = [A,B,D,E,I,J,K]

because 'B' comes after 'A' and before 'D'. So the insertion index would be 1 in this case.

I'm not sure if I explained the problem clearly, but I'd like to know a good approach that finds an insertion index.

No duplicate!

CodePudding user response：

If the items are unique (only can occur once), and are not comparable to each other (don't know that B comes after A), then.

1. Iterate through the rules and find the items position in the rule array.
2. Check if it is the first item in rules, if so insert at the first position and skip the other steps.
3. Check to see if it is the last item in rules, if so insert at the end and skip the other steps.
4. Select the value of the item 1 before into a variable A.
5. Select the value of the item 1 after into a variable B.
6. Iterate through the list, if you encounter the value in parameter A insert it after that value, if you encounter the value B, add the value before that.
7. If you come to the end without finding either value A or B, then you need to repeat but with values 2 before and 2 after the item in the rules (again checking to see if you hit the start or end of the rules list).

You will probably want to make 6 & 7 a function that calls itself recursively.

CodePudding user response：

Explained the Python code in comments. Basically, find the right place to insert the new element using binary search. The order of elements is decided using rank. The below code assumes that if elements is non-empty then the rule is followed by items in the elements.

rule = ['A','B','C','D','E','F','G','H','I','J','K']
rank = dict()
for i in range(len(rule)):
    rank[rule[i]] = i

elements = ['A','D','E','I','J','K'] #list in which we wish to add elements
target = 'B'    #element to be inserted

#Binary search to find the right place to insert the target in elements
left, right = 0, len(elements)
while left < right:
    mid = left   (right - left) // 2
    if rank[elements[mid]] >= rank[target]:
        right = mid
    else:
        left = mid   1

elements.insert(left, target) #left is the insertion index
print(elements)

Time complexity of add: O(log(len(elements))) 
Space complexity: O(1)

CodePudding user response：

A simple approach is, we can use one iteration of Insertion sort.

So, we start from right side of array compare our input x with array elements a go from right to left side. if we arrive an index i of array that let[i]<=x then let[i 1] is correct location that x can be insert. This approach that has time complexity O(n), follow from correctness of Insertion sort.

Note that the lower of your problem is O(n) because your data structure is array so you need after each insertion shift whole elements.