```
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int sorted = 0;
int cur = 1;
// 1: next one is greater than current sorted last element
// -1: next one is smaller than the current sorted last element
int state = 1;
int pos;
while (sorted < nums.size() - 1) {
if (cur == nums.size()) {
cur = sorted + 1;
}
// if there many elements with the same value between cur and sorted
if (cur != sorted + 1) {
// skip all element with the same value as sorted
while (nums[cur] == nums[sorted]) {
cur ++;
}
// if cur get the end of the array, let it go back to sorted + 1
if (cur == nums.size()) {
continue;
}
// if cur does not equals to nums[sorted], we can insert it into
// the sorted sequence.
if (state == 1) {
// the required next one is greater
// example 1: 2 5 3 3 4
// example 2: 2 5 3 3 2
if (nums[cur] > nums[sorted]) {
swap(nums[sorted + 1], nums[cur]);
sorted += 2;
} else {
swap(nums[sorted], nums[cur]);
sorted ++;
state = -1;
}
} else {
// the required next one is smaller
// example 1: 2 5 2 4 4 5
// example 2: 2 5 2 4 4 1
if (nums[cur] > nums[sorted]) {
swap(nums[sorted], nums[cur]);
sorted ++;
state = 1;
} else {
swap(nums[sorted + 1], nums[cur]);
sorted += 2;
}
}
cur ++;
} else {
// cur = sorted + 1
if (state == 1) {
// the required next one is greater
// example 1: 3 5 2 4
// example 2: 3 5 2 1
// example 3: 3 5 2 2
if (nums[cur] > nums[sorted]) {
sorted ++;
cur ++;
state = -1;
} else if (nums[cur] < nums[sorted]) {
swap(nums[sorted], nums[cur]);
sorted ++;
cur ++;
state = -1;
} else {
pos = search(nums, sorted - 2, state, nums[cur]);
if (pos != -1) {
swap(nums[pos], nums[cur]);
} else {
// if cannot find the appropriate position, just
// increase cur.
cur ++;
}
}
} else {
// example 1: 2 5 4 6 1
// example 2: 2 5 4 6 7
// example 3: 2 5 4 6 6
if (nums[cur] < nums[sorted]) {
sorted ++;
cur ++;
state = 1;
} else if (nums[cur] > nums[sorted]) {
swap(nums[sorted], nums[cur]);
sorted ++;
cur ++;
state = 1;
} else {
pos = search(nums, sorted - 2, state, nums[cur]);
if (pos != -1) {
swap(nums[pos], nums[cur]);
} else {
// if cannot find the appropriate position, just
// increase cur.
cur ++;
}
}
} // end of state = -1
} // end of cur = sorted + 1;
}
}
int search(vector<int>& nums, int pos, int flag, int value) {
// find the appropriate pos for condition: cur = sorte + 1, and
// nums[cur] = num[sorted]
while (pos >= 0) {
if (nums[pos] == value) {
pos -= 2;
} else {
if (flag == 1) {
if (pos == 0 || value < nums[pos - 1]) {
return pos;
} else {
pos -= 1;
flag = -1;
}
} else {
if (value > nums[pos - 1]) {
return pos;
} else {
pos -= 1;
flag = 1;
}
}
}
}
return -1;
}
};
```

- if the adjacent element is not equal, we can swap them and make the sequence wiggle before them.
- if the adjacent element is equal, if we can find a appropriate element which already in the wiggle sequence which can be exchange with the equal element, we go back to 1
- if cannot find such element, we increase cursor until no such element. We first use the different element insert to the subsequence with the same value, until cur=sorted+1, or cursor comes the end of the arrays.