First missing integer

1. Topics

Given an array A[0... N-1], find the first positive integer that is not in the array from 1.

Given 3, 5, 1, 2, -3, 7, 14, 8, output 4.

2. Analysis

There are two ways of thinking on this topic.

The first idea is based on bitmap idea. It opens up a new array B[0.N-1]. All elements of the array are initialized to 0 and traverse an array A once. If the element traversed is a positive integer I between 0 and N-1, then the element B[i] corresponding to subscript I is set to 1 in the B array. Finally, it traverses the B array and finds the first element whose value is 0. The subscript is the first positive integer that needs to be found that is not in the array.

This method has O(N) time complexity and O(N) space complexity.

If the original array is allowed to be modified, the second idea, the principle of cyclic invariants, can be derived.

The time complexity and space complexity of this algorithm are O(N) and O(1).

3. Code

int first_miss_number(int a[], int n){
    a--; // Let a count from 1
    int i = 1;
    while(i<=n){
        if(a[i] == i) i++;
        else if(a[i]<i || a[i]>n || a[i]==a[a[i]])
            a[i] = a[n--];
        else // a[i]>i
            swap(a[a[i]], a[i]);
    }   
    return i;
}

2. Finding the Minimum Value of Rotating Array

1. Topics

Assume that a sort array rotates with an unknown element as its fulcrum, such as: the original array 0 1 2 4 5 6 7 rotates to 4 5 6 7 0 1 2. Find the minimum value of the array after rotation. (Assuming there are no duplicate numbers in the array)

2. Analysis

The rotated array can actually be divided into two ordered sub-arrays: the size of the front sub-array is larger than that of the elements in the back sub-array;

4 5 6 7 0 1 2

Notice that the smallest element in fact is the dividing line between two subarrays.

As you can see, the idea of the algorithm is similar to the dichotomy search. The time complexity of the algorithm is O(logN), which is faster than traversing the array to get the minimum value.

3. Code

int find_min(int a[], int n){
    int low = 0;
    int high = n - 1;
    int mid;
    while(low<high){
        mid = (high + low) / 2; // Note that if the array is too large, this may cause an overflow
        if(a[mid]<a[high]) // The minimum is in the left half
            high = mid;
        else // The minimum is in the right half.
            low = mid + 1;
    }
    return a[low];
}

3. Zero subarray

1. Topics

For an array A of length N, find the values of the continuous subarray and the nearest zero.

For example: Array A, 1, - 2, 3, 10, - 4, 7, 2, - 5, which of all its subarrays is the closest to zero?
The answer is - 4, 7, 2, 5, and the sum is exactly 0.

2. Analysis

(1) Application for space sum[-1,0] 1 longer than A. N-1], sum[i] is the sum of the first I of A. (trick: define sum[-1] = 0)

Obviously:

(2) For sum[-1,0... N-1] sort and then calculate the absolute value of the difference between the adjacent elements of sum. The minimum value is required.

The time complexity of computing the first n terms, array sum and difference between adjacent elements of sum is O(N), and the time complexity of sorting is O(NlogN), so the total time complexity is O(NlogN).

Think: What if you need to return the subarray itself with the smallest absolute value?

In this case, a structure can be introduced, which contains two members, sum and pos, representing the preceding i and sum and POS at that location, namely pos=i. Then, the structure is sorted according to sum value, and the POS values of the two structures satisfying the absolute value of the difference between adjacent elements are taken. Then, the corresponding elements are output in the array according to the two POS values, that is, the zero and the array.

3. Code

typedef struct{
    int sum;
    int pos;
}SUM;

/**
 * Finding Zero and Array
 * Returns the value closest to zero, low is zero and the subscript of the first element of the array, high is zero and the subscript of the last element of the array.
 */
int zero_subarray(int a[], int n, int &low, int &high){
    SUM b[n];
    b[0].sum = a[0];
    b[0].pos = 0;
    for(int i=1; i<n; i++){
        b[i].sum = b[i-1].sum + a[i]; 
        b[i].pos = i;
    }
    cout<<"Before sorting:"; print_sum(b, n);
    // Sort (implementation details of sort are omitted here)
    sum_sort(b, n);
    cout<<"After sorting:"; print_sum(b, n);
    // Calculate the two sum with the smallest difference
    int diff, result = b[1].sum - b[0].sum;
    low = min(b[0].pos, b[1].pos);
    high = max(b[0].pos, b[1].pos);
    for(int i=1; i<n; i++){
        diff = abs(b[i].sum - b[i-1].sum);
        if(diff < result){  // To update
            result = diff;
            low = min(b[i].pos, b[i-1].pos);
            high = max(b[i].pos, b[i-1].pos);
        }
    }
    return result;
}

/**
 * Print Zero and Array
 */
void print_zero_subarray(int a[], int n, int low, int high){
    int i;
    for(i=low+1; i<high; i++)
        cout<<a[i]<<",";
    cout<<a[i]<<endl;
}

/**
 * Print an array of SUM structures
 */
void print_sum(SUM *b, int n){
    int i=0;
    for(i=0; i<n-1; i++)
        cout<<"("<<b[i].sum<<","<<b[i].pos<<"), ";
    cout<<"("<<b[i].sum<<","<<b[i].pos<<")"<<endl;
}

/**
 * Principal function
 */
int main(){
    int a[] = {1,-2,3,10,-4,7,2,-5};
    int n = 8;
    int low, high;
    cout<<"The sum closest to zero:"<<zero_subarray(a, n, low, high)<<endl;
    cout<<"The zero-sum array is:";
    print_zero_subarray(a,n,low,high);
    return 0;
}

The output results are as follows:

Before sorting: (1,0), (-1,1), (2,2), (12,3), (8,4), (15,5), (17,6), (12,7)
After sorting: (-1,1), (1,0), (2,2), (8,4), (12,3), (12,7), (15,5), (17,6)
The closest sum to 0:0
The zero-sum array is -4, 7, 2, -5.

4. Maximum Subarrays and

1. Topics

Given an array A[0,... n-1], find the continuous subarray of A, so that the sum of the subarray is maximum.

For example:
Array: 1, - 2, 3, 10, - 4, 7, 2, - 5,
Maximum subarrays: 3, 10, -4, 7, 2
Maximum subarray and:18

2. Analysis and Code

This problem can be solved by using the idea of dynamic programming (optimal sub-problem). The time complexity is O(N). The algorithm steps are as follows:

If S[i] is the largest subarray in an array ending with A[i], then:

• Initialize result to A[0], S[0] = A[0]
• Traversing i i n the range of I [1, n], if S [i-1] > 0, then S[i] = S[i-1] + A[i]
• If S [i-1] <== 0, then S[i] = A[i]
• The maximum subarray at this point is: result = max(result, S[i])

The code is as follows:

/**
 * Solving Maximum Subarrays and Arrays
 */
int max_subarray(const int a[], int n){
    if(!a || n<=0) return 0;
    int sum = a[0];
    int result = sum; // Record the current optimal solution
    for(int i=1; i<n; i++){
        if(sum>0) sum+=a[i];
        else sum = a[i];
        result = max(sum, result);
    }
    return result;
}

Think: What should we do if we need to output the maximum subarray itself in addition to the sum of the largest subarrays?

At this point, two flags from and to can be set to represent the starting and ending points of the maximum subarray.
Remember that sum is not the largest subarray in an array ending with A[i], then:

• Initialize result to A[0], sum = A[0], from = to = 1, - 1 means no element
• Traversing i i n the range of I [1, n], if sum > 0, then sum = sum + A[i]
• If sum <= 0, then sum = A[i], record from_new = i
• If the result < sum, that is, the current sum value is the optimal solution, update the starting point from and the ending point to, from = from_new, to = i,

The element of the output array A[n] from from from to is the largest subarray.

The code is as follows:

/**
 * Solving the maximum subarray and the maximum subarray itself
 */
int max_subarray_pos(const int a[], int n, int &from, int &to){
    if(!a || n<=0){
        from = to = -1;
        return 0;
    }
    int sum = a[0];
    int result = sum; // Record the current optimal solution
    from = to = 0;
    int from_new; // New Subarray Starting Point
    for(int i=1; i<n; i++){
        if(sum>0) sum+=a[i];
        else{ // The starting point of the largest subarray has changed
            sum = a[i];
            from_new = i;
        }
        if(result < sum){ 
        // The current maximum is greater than the result, changing the starting point from the optimal solution to from_new and the ending point to i
            result = sum;        
            from = from_new;
            to = i;
        }
    }
    return result;
}

// Output maximum subarray code
for(i=from; i<to; i++)
        cout<<a[i]<<",";
cout<<a[i]<<endl;

V. Maximum Interval

1. Topics

Given the integer array A[0... N-1], find the maximum interval after sorting the N numbers.

For example, the maximum interval of 1, 7, 14, 9, 4, 13 is 4.
After sorting: 1, 4, 7, 9, 13, 14, the maximum interval is 13-9 = 4

Obviously, sorting the original array and then finding the maximum value of the latter subtracting the former is the solution, and the time complexity is O(nlogn). Is there a better way?

(If you change the conditional integer array into a floating-point array, the title will be simpler. Note: It's simpler. Why?

2. Analysis

The time complexity of this method is O(n).
(It can also be seen from the above that if the dry condition is changed to a floating-point array, the title will be better able to calculate the number and size of buckets and allocate array elements.)

3. Code

/**
 * bucket
 */
typedef struct Bucket{
    bool isEmpty;
    int min;
    int max;
    Bucket() : isEmpty(true) {}
    void add(int k){
        if(isEmpty){
            min = max = k;
            isEmpty = false;
        } else{
            if(max < k) max = k;
            if(min > k) min = k;
        }
    }
}Bucket;

/**
 * Calculating the Maximum Spacing
 */
int calc_max_gap(const int a[], int n){
    Bucket bucket[n];
    // Calculate the maximum of array a
    int max = a[0], min = a[0], i;
    for(i=0; i<n; i++){
        if(max < a[i]) max = a[i];
        if(min > a[i]) min = a[i];
    }
    // Put the data in buckets in turn
    int delta = max - min;
    int num; // Mark which bucket the number should be in
    for(i=0; i<n; i++){
        num = (a[i] - min) * n / delta;
        if(num >= n) num = n-1;
        bucket[num].add(a[i]);
    }
    // Calculating effective barrel
    i = 0;
    int gap = delta / n;  // Initialize the minimum spacing to the barrel spacing
    int t;
    for(int j=1; j<n; j++){ // i is the former bucket and j is the latter bucket
        if(!bucket[j].isEmpty){ // The barrel is not empty
            t = bucket[j].min - bucket[i].max;
            gap = gap > t ? gap : t;
            i = j;
        }
    }
    return gap;
}