Saturday, September 26, 2009

fix duplicates in sorted array

12233344445 -> 12345

//using 3 pointers
fixDuplicatesInSortedArray(int[] a):
    start = 0
    destination = 0
    end = 0
    while (end < a.Length):
        while (end < a.Length && a[end] == a[start]):
            end++
        a[destination++] = a[start]
        start = end
    
    while (destination < a.Length):
        a[destination++] = null
    return

//using 2 pointers
fixDuplicatesInSortedArray(int[] a):
    curr = 0
    index = 0
    while (index < a.Length):
        while (index +1 < a.Length && a[index] == a[index +1]):
            index++
        a[curr] = a[index]
        curr++
        index++
    while (curr < a.Length):
        a[curr++] = 0
    return    


[Hat tip to MG]

No comments:

Post a Comment