java程序员进大厂算法面试中的首尾指针技巧

指针首尾并进

快排分割数组首尾的实现方式。
输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
输入一个增序数组和一个数sum，在数组中找到两个数，使得和为sum。输入任意一对即可。

1、思路：

先随机选base，与尾交换。然后从左往右遍历，找到比base大的数，交换；从右往左遍历，找到比base小的数，交换。

#include <iostream> 
#include <exception> 
#include <stdlib.h> 
#include <string.h> 

using namespace std; 

int RandInRange(int a, int b) { 
    return rand()%(b - a + 1) + a; 
} 

void PrintArray(int data[], int length) { 
    for (int i = 0; i < length; i++) 
    printf("%d ", data[i]); 
    printf("\n"); 
}

int Partition(int data[], int length, int start, int end) { 
    if (data == NULL || length <= 0 || start < 0 || end >= length) 
    throw new exception(); 

    int index = RandInRange(start, end); 
    int base = data[index]; 
    swap(data[start], data[index]); 

    while(start < end) { 
        while (start < end && data[end] > base) 
        end--; 
        data[start] = data[end]; 
        while (start < end && data[start] < base) 
        start++; 
        data[end] = data[start]; 
    } 

    data[start] = base; 
    return start; 
} 

void QuickSort(int data[], int length, int start, int end) { 
    if (start == end) 
    return; 
    int index = Partition(data, length, start, end); 
    if (index > start) 
    QuickSort(data, length, start, index - 1); 
    if (index < end) 
    QuickSort(data, length, start + 1, end); 
} 

int main() { 
    int test[7] = {23, 13, 49, 6, 31, 19, 28}; 
    PrintArray(test, 7); 
    QuickSort(test, 7, 0, 6); 
    PrintArray(test, 7); 60 
}

2、思路：

设置两个指针，首尾位置。首指针往后移直到遇到偶数，尾指针往前移直到遇到奇数，两者都遇到的情况下互换位置，终止条件是首尾指针碰头。

void ReorderOddEven(int *pData, unsigned int length) { 
    if(pData == NULL || length == 0) 
    return; 

    int *pBegin = pData; 
    int *pEnd = pData + length - 1; 

    while(pBegin < pEnd) { 
        // 向后移动pBegin，直到它指向偶数 
        while(pBegin < pEnd && (*pBegin & 0x1) != 0) 
        pBegin ++; 

        // 向前移动pEnd，直到它指向奇数 
        while(pBegin < pEnd && (*pEnd & 0x1) == 0) 
        pEnd --; 

        if(pBegin < pEnd) { 
        int temp = *pBegin; 
        *pBegin = *pEnd; 
        *pEnd = temp; 
        } 
    } 
}

3、思路：

如果原数组是无序的，则先排序，O(nlogn)开销。这里已经是增序排列了，所以不需要排序。设置两个指针，一头一尾。当和大于s，尾指针往前移；当和小于s，头指针往后移。直到两指针相遇，看是否有符合要求的数出现。

FindNumbersWithSum 
bool FindNumbersWithSum(int data[], int length, int sum, int *num1, int *num2) { 
    bool found = false; 
    if (length < 1 || num1 == NULL || num2 == NULL) 
    return found; 
    int ahead = length - 1; 
    int behind = 0; 
    while (ahead > behind) { 
        long long curSum = data[ahead] + data[behind]; 
        if (curSum == sum) { 
            *num1 = data[behind]; 
            *num2 = data[ahead]; 
            found = true; 
            break; 
        } else if (curSum > sum) 
            ahead--; 
            else 
            behind++; 
    } 
    return found; 
}

最后总结

能用首尾指针技巧解决的问题，往往序列是存在规律的，但其实这种要求并不严格
但是要求首尾指针根据制定的规则往中间移动的过程中，一定不会错过答案
制定的规则与数据状况和问题本身相关

左程云左神：算法面试中的首尾指针技巧

ps：不了解左神的朋友可以去百度一下

1：介绍首尾指针技巧

2：详解两道利用首尾指针技巧解决的题

左程云左神的《程序员代码面试指南 IT名企算法与数据结构题目最优解》

目录（算法有分将、校、尉、士四个等级来表示难易程度）

第1章栈和队列

设计一个有getMin功能的栈(士★)

由两个栈组成的队列(尉★★)

如何仅用递归函数和栈操作逆序一个栈(尉★★)

猫狗队列(士★)

用一个栈实现另一个栈的排序(士★)

用栈来求解汉诺塔问题(校★★★)

生成窗口最大值数组(尉★★)

构造数组的MaxTree (校★★★)

求最大子矩阵的大小(校★★★)

最大值减去最小值小于或等于num的子数组数量(校★★★)

限于篇幅原因，同时也为了大家更好的阅读，只截取了部分目录，感兴趣的朋友可以帮忙转发文章后，关注私信回复【学习】来免费获取