CODEWITHSUNDEEP
pythonlistnumbersnested-lists
Ros
Ros

Reputation: 7

split a num list into sublists with consecutive numbers

I want to group numbers in a numeric list into sublists. In the sublists must be the consecutive numbers

input ==> [-4,-3,-2,0,1,3,5,6,7,17,18,30] output ==> [[-4,-3,-2],[0,1],[3],[5,6,7],[17,18],[30]]

Preferably without libraries (only the generics)

Upvotes: -2

Views: 1152

Answers (4)

user28235986
user28235986

Reputation: 1

You can use binary search to find the maximum index of the last contiguous value in a list of numbers. Binary search is an efficient method to find an element's position, and we can use it to identify the end of a continuous sublist by comparing values with their respective indices.

# Binary search to find the end of the continuous sequence
def find_max_continuous_index(arr):
    n = len(arr)
    left, right = 0, n - 1
    while left < right:
        mid = (left + right + 1) // 2
        if arr[mid] == arr[0] + mid:
            left = mid
        else:
            right = mid - 1

    return left

continuous_sublists = []
start = 0

while start < len(input):
    end = find_max_continuous_index(input[start:]) + start
    continuous_sublists.append(input[start:end + 1])
    start = end + 1

Upvotes: 0

Thane Brooker
Thane Brooker

Reputation: 431

Generators can be good for this sort of thing.

Code

def group_me(list):
    list.sort()
    sublist = []

    while list:
        v = list.pop(0)

        if not sublist or sublist[-1] in [v, v-1]:
            sublist.append(v)
        else:
            yield sublist
            sublist = [v]

    if sublist:
        yield sublist


list = [-4, -3, -2, 0, 1, 3, 5, 6, 7, 17, 18, 30]
result = [sublist for sublist in group_me(list)]
print(result)

Output

[[-4, -3, -2], [0, 1], [3], [5, 6, 7], [17, 18], [30]]

Notes

If there are duplicates in the input list, it puts them into the same sublist.

Upvotes: 3

Yukun Li
Yukun Li

Reputation: 254

two pointer solution

a = [-4,-3,-2,0,1,3,5,6,7,17,18,30]
slow, fast = 0,0
ans, temp = [], []
while fast < len(a):
    if fast - slow == a[fast] - a[slow]:
        temp.append(a[fast])
        fast += 1
    else:
        slow = fast
        ans.append(temp)
        temp = []
if fast > slow:
    ans.append(temp)
print(ans)

Upvotes: 1

CDJB
CDJB

Reputation: 14546

To do this, you can simply use a for loop. One pass is the best we can do - we have to look at each element once. This is O(n) in big-O notation.

Remember that the list must be sorted, otherwise it will not work.

Code:

inpt = [-4,-3,-2,0,1,3,5,6,7,17,18,30]

rv = []

# Set up current list with first element of input
curr = [inpt[0]]

# For each remaining element:
for x in inpt[1:]:
    # If the next element is not 1 greater than the last seen element
    if x - 1 != curr[-1]:
        # Append the list to the return variable and start a new list
        rv.append(curr)
        curr = [x]
    # Otherwise, append the element to the current list.
    else:
        curr.append(x)
rv.append(curr)

Output:

>>> rv
[[-4, -3, -2], [0, 1], [3], [5, 6, 7], [17, 18], [30]]

Upvotes: 2

Related Questions