本文共 2599 字，大约阅读时间需要 8 分钟。

删除有序数组中的重复项

问题描述：

给你一个有序数组 nums，请你在原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组，并在使用 O(1) 额外空间的条件下完成。

解析：

考虑使用两个指针，prev 表示当前位置的元素为不含重复元素数组的最后一个元素的位置，另一个指针遍历数组。由于数组是有序的，因此相同的元素都会相邻出现。当两个元素不相等时，将遍历指针的元素填入不含重复数组之内。由于 prev 指向的是不含重复元素数组的最后一个元素的位置，返回时需要 +1 才是真实数组的大小。这种方法只需遍历一遍数组，时间复杂度为 O(N)，空间复杂度为 O(1)。

代码示例：

public int removeDuplicates(vector
   
     &nums) {    if (nums.size() == 0) return 0;    int prev = 0;    int next = 1;    while (next < nums.size()) {        if (nums[next] != nums[prev]) {            prev++;        }        next++;    }    return prev + 1;}
   

---

只出现一次的数字2

问题描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

解析：

由于其他数字都出现了三次，我们可以统计每个比特位的 1 的个数，然后对 3 取余，找出哪个位上有单独的 1。根据该位的位置，将所有符合的值加起来即可得到结果。

代码示例：

public int singleNumber(vector
   
     &nums) {    int ret = 0;    for (int i = 0; i < 32; i++) {        int bit = 0;        for (auto e : nums) {            bit += (e >> i) & 1;        }        ret += (bit % 3) << i;    }    return ret;}
   

---

只出现一次的数字 III

问题描述：

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出这两个只出现一次的元素。你可以按任意顺序返回答案。

解析：

将所有数都异或，得到出现一次的数的异或结果。

在得到的结果中找到 bit 位为 1 的位置，记录下来。

根据 bit 位为 1 的位置，将数组分为两组，再进行异或即可得到最终结果。

代码示例：

public vector
   
     singleNumber(vector
    
      &nums) {    int val = 0;    for (auto e : nums) {        val ^= e;    }    if (val == 0) {        return nums;    }    int count = 0;    while (1) {        if ((val >> count) & 1 == 1) {            break;        }        count++;    }    int num1 = 0;    int num2 = 0;    for (auto e : nums) {        if ((e >> count) & 1 == 1) {            num1 ^= e;        } else {            num2 ^= e;        }    }    vector
     
       ret;    ret.push_back(num1);    ret.push_back(num2);    return ret;}
     
    
   

---

数组中出现次数超过一半的数字

问题描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如，输入一个长度为 9 的数组 {1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。

解析：

给定一个变量 prev 标记当前的数字，给定一个 count 记录当前数字剩余个数。当遍历数组，元素和 prev 相等，计数器 +1。如果不相等，计数器 -1；当计数器为零时，我们换下一个标记元素。由于是两两抵消的，如果数组元素个数是偶数，那么最后剩下的元素就是超过数组一半的元素。如果元素个数是奇数，最后还需要循环判断一次。

代码示例：

public int MoreThanHalfNum_Solution(vector
   
     &numbers) {    if (numbers.size() == 0) return 0;    int prev = numbers[0];    int count = 1;    for (int i = 1; i < numbers.size(); i++) {        if (numbers[i] == prev) {            count++;        } else {            count--;        }    }    if (count > 0) {        int half = numbers.size() / 2;        if (count > half) {            return prev;        }    }    for (int i = 0; i < numbers.size(); i++) {        if (numbers[i] == prev) {            return prev;        }    }    return 0;}