C++实现一维数组按元素范围分组为二维数组及vector适用性探讨

Absolutely! This is a straightforward grouping problem, and we can build an algorithm that perfectly matches your expected output. Let's break this down:

1. Algorithm Logic #

The core idea is to iterate through the 1D array, building subarrays where the range (max value - min value) of elements in each subarray never exceeds 10. Here's a step-by-step breakdown of how to implement this:

• Start by checking if the input array is empty (handle edge cases first!). If it is, return an empty 2D array.
• Initialize your first subarray with the first element of the input, and track the current subarray's minimum and maximum values (this avoids re-scanning the subarray every time to check bounds).
• For each subsequent element:
  • If adding the element keeps the subarray's range ≤10, add it to the current subarray and update the min/max values if needed.
  • If the element would push the range over 10, finalize the current subarray, add it to the result, and start a new subarray with this element.
• Don't forget to add the last subarray to the result once the loop finishes!

C++ Implementation with vector #

Here's a working code example that follows this logic:

#include <vector>
#include <cstdlib> // For abs()

using namespace std;

vector<vector<int>> groupIntoSubarrays(const vector<int>& input) {
    vector<vector<int>> result;
    if (input.empty()) return result;

    vector<int> currentGroup;
    currentGroup.push_back(input[0]);
    int currentMin = input[0];
    int currentMax = input[0];

    for (size_t i = 1; i < input.size(); ++i) {
        int num = input[i];
        // Check if the number fits in the current group's range
        if (abs(num - currentMin) <= 10 && abs(num - currentMax) <= 10) {
            currentGroup.push_back(num);
            // Update min/max for the current group
            if (num < currentMin) currentMin = num;
            if (num > currentMax) currentMax = num;
        } else {
            // Finalize current group and start a new one
            result.push_back(currentGroup);
            currentGroup.clear();
            currentGroup.push_back(num);
            currentMin = num;
            currentMax = num;
        }
    }
    // Add the last remaining group
    result.push_back(currentGroup);
    return result;
}

When you run this with your input {21,23,24,45,43,63,65,66}, it will produce exactly your expected output:
{{21,23,24},{45,43},{63,65,66}}

2. Is Using vector the Right Choice? #

Absolutely—vector is perfect for this task in C++. Here's why:

• Dynamic sizing: Subarrays can vary in length (like your second subarray only has 2 elements), and vector automatically handles resizing as you add elements, no need to pre-allocate fixed sizes.
• Memory management: vector takes care of memory allocation/deallocation behind the scenes, so you don't have to worry about leaks or manual array management.
• Efficiency: Accessing elements in a vector is O(1) (just like a raw array), and adding elements to the end is amortized O(1), making this algorithm efficient even for larger arrays.
• Flexibility: You can easily modify the logic (like sorting first if needed) and vector will adapt seamlessly.

If you used a raw 2D array instead, you'd have to guess the number of subarrays and their lengths upfront, which is impractical here. vector solves all those headaches.

内容的提问来源于stack exchange，提问作者Michael Helmbrecht