Find Smallest Positive Number

LowestInt.cpp

#include <stdio.h>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

struct MinMax {
    int min;
    int max;
    MinMax(int min, int max): min(min), max(max) {}
};

MinMax minMaxPositiveIndex(vector<int>& nums) {
    int min = std::numeric_limits<int>::max();
    int max = 0;
    int minRes = 0;
    int maxRes = 0;
    
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0 && nums[i] <= min) {
            minRes = i;
            min = nums[i];
        }
        if (nums[i] > max) {
            max = nums[i];
            maxRes = i;
        }
    }
    return MinMax(minRes, maxRes);
}

void swap(vector<int>& nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

int dividedByMinPositiveIndex(vector<int>& nums) {
    int i = 0;
    int j = int(nums.size());
    int lo = nums.front();
    while (true) {
        while (nums[++i] < lo)
            if (i == nums.size() - 1) break;
        while (nums[--j] > lo)
            if (j == 0) break;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, 0, j);
    return j;
}

int reArrange(vector<int>& nums, int lo, int hi, int min, int max) {
    int i = lo;
    while (i <= hi) {
        int val = nums[i];
        int realIndex = nums[i] - min + lo;
        
        if (realIndex < i) {
            nums[realIndex] = val;
            nums[i] = -1;
            i++;
            continue;
        } else if (realIndex == i) {
            i++;
            continue;
        } else if (realIndex > i && realIndex <= hi) {
            swap(nums, realIndex, i);
            continue;
        } else if(realIndex > hi) {
            nums[i] = -1;
            i++;
            continue;
        }
    }
    
    for (int i = lo; i <= hi; i++) {
        if (nums[i] == - 1) {
            return i - lo + min;
        }
    }
    
    return max + 1;
}

int lowestInteger(vector<int>& nums) {
    MinMax minAndMax = minMaxPositiveIndex(nums);
    int min = nums[minAndMax.min];
    int max = nums[minAndMax.max];
    if (min > 1) {
        return 1;
    }
    swap(nums, 0, minAndMax.min);
    int newMinIndx = dividedByMinPositiveIndex(nums);
    return reArrange(nums, newMinIndx, int(nums.size()) - 1, min, max);
    
}

int main(int argc, const char * argv[]) {
    printf("Dang chay \n");
    vector<int> vect{ 4,3,2,1,5,6,7, 10, 20, 30 };
    int result = lowestInteger(vect);
    printf("Result: %d \n", result);
    return 0;
}