Skip to content

关于题解一源码分析的i >= right条件 #112

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
billryan merged 1 commit into from
May 19, 2018
Merged

关于题解一源码分析的i >= right条件 #112

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
12 changes: 7 additions & 5 deletions zh-hans/integer_array/partition_array.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -43,10 +43,12 @@ public:
int right = 0;
const int size = nums.size();
for (int i = 0; i < size; ++i) {
if (nums[i] < k && i >= right) {
int temp = nums[i];
nums[i] = nums[right];
nums[right] = temp;
if (nums[i] < k) {
if (i != right) {
int temp = nums[i];
nums[i] = nums[right];
nums[right] = temp;
}
++right;
}
}
Expand All @@ -58,7 +60,7 @@ public:

### 源码分析

自左向右遍历，遇到小于 k 的元素时即和`right`索引处元素交换，并自增`right`指向下一个元素，这样就能保证`right`之前的元素一定小于 k. 注意`if`判断条件中`i >= right`不能是`i > right`, 否则需要对特殊情况如全小于 k 时的考虑，而且即使考虑了这一特殊情况也可能存在其他 bug. 具体是什么 bug 呢？欢迎提出你的分析意见~
自左向右遍历，遇到小于 k 的元素时即和`right`索引处元素交换，并自增`right`指向下一个元素，这样就能保证`right`之前的元素一定小于 k.

### 复杂度分析

Expand Down