数组中的解题技巧

双指针

双指针能够将$O(n^2)$复杂度的算法降低为$O(n)$，并且常见于原地算法。两个指针能够在一个for循环内完成两个for循环的工作。

同向指针

283.移动零

void moveZeroes(int* nums, int numsSize) {
    int slow = 0;

    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] != 0)       //不要判断nums[i] == 0，否则会很麻烦
        {
            nums[slow] = nums[i];
            slow++;
        }
    }

    for (int i = slow; i < numsSize; i++)
    {
        nums[i] = 0;
    }
}

在这里，slow作为慢指针，用于指示去掉0之后的“新元素”，而循环中的i作为快指针，负责处理遍历。快指针走的比慢指针快，因此慢指针对元素做的原地处理不会和后面的快指针操作发生冲突。

27.移除元素

int removeElement(int* nums, int numsSize, int val) {
    //int fast = 0;
    int slow = 0;

    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] != val)
        {
            nums[slow] = nums[i];
            slow++; 
        }
    }

    return slow;
}

思路和上一题相同。主要判断条件都是“不等于”，因为slow要指向的对象是待储存元素（slow要重新在数组内为这些元素分配位置），而不是等于val的元素。

26.删除有序数组中的重复项

int removeDuplicates(int* nums, int numsSize) {
    int current_pos = 1;
    for (int i = 1; i < numsSize; i++)
    {
        if(nums[i] != nums[i-1])    
        {
            nums[current_pos] = nums[i];    
            current_pos++;
        }
    }

    return current_pos;
}

思路也是一致的，判断出当前元素是否和前一个不一致，如果不一致说明这个元素要保留，slow就会指向这个元素。

349.两个数组的交集
这题的分为两个部分：排序+双指针。双指针法只需要一次循环，前提是数组必须经过排序。排序完后的数组是升序的，两个数组分别使用两个指针从首位开始向后遍历并比较。以这两个数组为例：

[4,9,5]
[9,4,9,8,4]

排序之后的结果为

[4,5,9]
[4,4,8,9,9]

两个指针分别开始遍历，如果指针1指向值大于指针2指向值，说明指针2位置偏左，对其++；如果指针1指向值小于指针2指向值，则说明指针1偏左，对其++；如果指针1和指针2指向值大小相等，该值属于交集，提出并保存在result中。

这个做法会带来重复存入的问题，比如上面的算例中，result会先后存入两个4。为了避免该情况发生，在存入时需要做过滤，条件为result中待存入位置的前一个数不能等于当前要存入的这个数（result[k-1] != nums1[i]。如果待存入位置是result的第一位，则不用判断，直接存入k == 0。因为两个数组事先已经排过序，所以这个判断逻辑一定是正确的，不存在漏判断的问题。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int compare(const void *a, const void *b){
    return *(int *)a - *(int *)b;
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    qsort(nums1, nums1Size, sizeof(int), compare);
    qsort(nums2, nums2Size, sizeof(int), compare);
    int i = 0;
    int j = 0;
    int k = 0;
    int* result = malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));

    while (i < nums1Size && j < nums2Size){
        if (nums1[i] > nums2[j]){
            j++;
        }
        else if (nums1[i] < nums2[j]){
            i++;
        }
        else if (nums1[i] == nums2[j]){
            if (k == 0 || result[k - 1] != nums1[i]){
                result[k++] = nums1[i];
            }
            i++;
            j++;
        }
    }

    *returnSize = k;
    return result;
}

排序

冒泡排序

void bubble_sort(int* nums, int numsSize)
{
    for (int i = 0; i < numsSize - 1; i++)
    {
        for (int j = 0; j < numsSize - 1 - i; j++)
        {
            if (nums[j] > nums[j + 1])
            {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

快速排序

其他

Boyer-Moore 投票算法（众数问题）

Boyer-Moore 投票算法是一种用于寻找**众数（Majority Element）**的高效算法。众数定义为一个数组中出现次数超过总长度一半的元素。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。核心思想是利用计数器（count）维护当前候选元素的“优势”，如果某个元素在整个数组中出现次数超过一半，算法最终能锁定这个元素。

步骤为：

1. 候选阶段：

   • 从数组的第一个元素开始，假设它是众数候选人（candidate）。
   • 遍历数组，如果当前元素与候选人相同，增加计数器（count++）；如果不同，减少计数器（count--）。
   • 当计数器为零时，重新选择下一个元素作为新的候选人。

2. 确认阶段（可选，视问题需求而定）：

   • 如果题目明确保证数组中一定有众数，则跳过此步骤，候选人即为众数。
   • 如果不保证众数存在，需要再遍历一次数组，验证候选人的出现次数是否超过数组的一半。

169.多数元素

int majorityElement(int* nums, int numsSize) {
    int count = 0;      /* 计数器 */
    int candidate = 0;  /* 候选人 */

    for (int i = 0; i < numsSize; i++){
        if (count == 0){        /* 如果计数器为0，选中当前元素为候选人 */
            candidate = nums[i];
            count = 1;
        }else if (nums[i] == candidate){    /* 如果当前元素为候选人 */
            count++;
        }else{
            count--;
        }
    }

    return candidate;
}