利用数组下标来充当指针。
1.双指针算法本质: 将数据划分为三个区间,我们以移动零为例: 给定数组中。 【0,left】:全是非0元素。 【left+1,cur-1】:全是0元素。 【cur,n-1】:待处理元素。
public void moveZeroes(int[] nums) {
//定义left和right双指针。并在right<n的情况下循环。
//如果nums[right] != 0则交换left和right指向的元素。
//若等于零则right++。
//保证left之前的数据非零。left指向第一个零。
//right之后的数据待处理。
int left = 0,right = 0;
int n = nums.length;
while(right < n){
if(nums[right] != 0){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
}
right++;
}
}
快排里面最核心的一步就是数据划分这一步。 定义一个数组,我们设置一个基准元素tmp。将数组划分为两个部分。 左边全 <= tmp。 右边全 > tmp。 三个区间: 【0,left】:全是 ≤ tmp。 【left+1,cur-1】:全是 > tmp。 【cur,n-1】:待处理元素。 快排的双指针思想不适合处理很多数据都相同的情况。
后面有一道颜色划分的题目。 我们会把数组分成三块。用这个算法排序思想来解决快排是最好的解法。