How many cross lines in unsorted array


  • 0
    U

    The title of the question is not complete. Here is explanation:
    Given an unsorted array. for example [2, 3, 1, 4, 5].
    Sort the array, we have new array [1, 2, 3, 4, 5],
    if we draw the line between the 2 arrays for the same number, for example:

    [3, 2, 1,4,5]
      \ | /
       \|/
       /|\
    [1, 2, 3,4,5]
    

    then we have 3 line-cross:

    1. line (1 to 1) cross line (2 to 2)
    2. line (1 to 1) cross line (3 to 3)
    3. line (2 to 2) cross line (3 to 3)

    Implement the algorithm to calculate the how many line crosses for an unsorted array.


  • 0
    B

    my solution is

    • Find all elements that will not moved after sort.
    • Check every elements got in step 1, if every elements before it less than it. it's a element who doesn't cross, count 1
    • Use list's size minus no cross number
    def number_of_cross(list):
        sl = list[:]
        sl.sort()
        noCross = 0
    
        for i in range(len(list)):
            if sl[i] == list[i]:
                allLess = True
                for j in range(i):
                    if list[j] > list[i]:
                        allLess = False
                        break
    
                if allLess:
                    noCross = noCross + 1
    
        return len(list) - noCross
    
    if __name__ == "__main__":
        print(number_of_cross([3, 2, 1, 4, 5]))

  • 0
    U

    @billyean ,
    if the array is [4, 3, 2, 1], the number of line crosses is 3+2+1=6. So the solution is incorrect.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.