Python Exercise of Dividing Arrays into Consecutive Numbers

Catalog 1, Problem Description 2, Solution 3, Conclusion

This article is transferred from WeChat official account: "Beauty of Algorithm and Programming"

1. Problem description

Give you an array of integers nums And 1 positive integer k Please determine whether this array can be divided into 1 groups by k A collection of consecutive numbers.

If you can, please return True ; Otherwise, return False .

Example 1:

Enter: nums = [1,2,3,3,4,4,5,6], k = 4

Output: true

Explanation: Arrays can be divided into [1, 2, 3, 4] and [3, 4, 5, 6].

Example 2:

Enter: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3

Output: true

Explanation: Arrays can be divided into [1, 2, 3], [2, 3, 4], [3, 4, 5], and [9, 10, 11].

Example 3:

Enter: nums = [3,3,2,2,1,1], k = 3

Output: true

Example 4:

Enter: nums = [1,2,3,4], k = 3

Output: false

Explanation: An array cannot be divided into several sub-arrays of size 3.

2. Solutions

Just got this problem, the author wants to find out the smallest number in the array first, and then delete the corresponding elements from the array according to the value of k. For example, if k is equal to 3 and the smallest number in the array is 1, then delete 1, 2 and 33 elements from the list. If there is no corresponding element in the array, then return False.

The following problem is solved:

def isPossibleDivide(nums, k):
     nums = sorted(nums)
     for _ in range(len(nums)//k):
         minv = nums[0]
         for _ in range(k):
             if minv in nums:
                 nums.remove(a)
                 minv +=1
     return len(nums) == 0
 
 

But in the second for There are too many operations in the loop. If the value of k is too large, the code running memory will be very large, and it will time out when running in the specified memory. Therefore, the author thought of the second method. Although the code amount is 1 point larger, compared with the first method, the time complexity is smaller, and it is not easy to time out. Use the set to find out the numbers that have appeared in the array, then use the dictionary to count the number of occurrences of each number, set the judgment conditions, and then return the corresponding Boolean type according to the continuous judgment conditions.

python code:

def isPossibleDivide(nums, k):
     n = len(nums)
     if n % k != 0:
         return False
     #  Record possible numbers with sets 
     s = set(nums)
     minList = list(s)
     minList.sort()
     #  Store the number of occurrences of each number in a dictionary 
     d = dict()
     for num in nums:
         if num not in d:
             d[num] = 0
         d[num] += 1
     #  Determine whether each group can be determined by k Composed of consecutive numbers 
     m = n // k  # m Group 
     start = 0  #  Starting position 
     for mi in range(m):
         if start >= len(minList):
             return False
         minv = minList[start]
         flag = True
         t = start
         for key in range(minv, minv +  k):
             if key not in d:
                 return False
             if d[key] < 1:
                 return False
             elif d[key] == 1:
                 d[key] -= 1
                 t += 1
             elif d[key] > 1:
                 d[key] -= 1
                 if flag:
                     start = t
                     flag = False
         if flag:
             start = t
     return True

3. Conclusion

When encountering this kind of programming problem, we should try to solve it by using various methods, and consider many factors such as time complexity and space complexity to find the optimal solution.