1 class Solution { 2 public: 3     int firstMissingPositive(vector<int>& nums) { 4         bucketSort(nums); 5         // 将下标为i处放置值为i+1的元素，输出不满足的第一个nums[i], 也有可能都满足，则是数组最后一个元素 + 1 6         for (int i = 0; i < nums.size(); ++i) { 7             if (nums[i] != i + 1) return i + 1; 8         }  9         return nums.size() + 1;10     }11 private:12     void bucketSort(vector<int>& nums)13     {14         // 总体思想是通过swap(a[i], a[a[i] - 1])，当a[i] = i + 1时，不需要交换，++i15         // 当a[i] > n, 或者a[i] <= 0, 应当选择不处理当前元素，因为没有可交换的元素下标，可能的后续交换过程会将其放到任意可能的位置16         // 当a[i] > i + 1时，swap()会将当前元素和后续所有交换的元素放到正确的位置上(如果后续交换的元素满足限制条件)17         // 当a[i] < i + 1时，因为i之前的元素都已经排序好，所以会有nums[i] == nums[nums[i] - 1], 始终保持不变，往前走 ++ i18         for (int i = 0; i < nums.size(); ++i) {19             while (nums[i] != i + 1) {20                 if (nums[i] > nums.size() || nums[i] <= 0 || nums[i] == nums[nums[i] - 1]) break;21                 else {22                     swap(nums[i], nums[nums[i] - 1]);23                 }24             }25         }26     }27 };