Java和C++如何在排序数组中查找数字出现的次数

# Java和C++如何在排序数组中查找数字出现的次数

## 引言

在计算机科学和软件开发中，处理排序数组是常见的任务之一。查找特定数字在排序数组中出现的次数不仅是一个经典的算法问题，也是面试中经常被问到的题目。本文将详细探讨在Java和C++中如何高效地解决这个问题，分析不同方法的优缺点，并提供完整的代码示例。

## 问题描述

给定一个已经排序的整数数组和一个目标数字，要求统计该目标数字在数组中出现的次数。例如：

- 输入数组: `[1, 2, 2, 2, 3, 4, 4, 5]`
- 目标数字: `2`
- 输出: `3` (因为数字2出现了3次)

## 方法概述

解决这个问题主要有三种方法：

1. **线性搜索法**：遍历整个数组，统计目标数字出现的次数。
2. **二分查找法**：利用二分查找找到目标数字的第一次和最后一次出现的位置，然后计算次数。
3. **库函数法**：使用语言内置的函数或库来简化实现。

本文将重点讨论前两种方法，并在Java和C++中分别实现它们。

---

## 方法一：线性搜索法

### 算法思路

线性搜索法是最直观的方法。我们从数组的第一个元素开始，逐个检查每个元素是否等于目标数字，并统计匹配的次数。

### 时间复杂度

- **最坏情况**：O(n)，其中n是数组的长度。
- **最好情况**：O(1)（目标数字在数组的第一个位置且只出现一次）。

### Java实现

```java
public class LinearSearch {
    public static int countOccurrences(int[] arr, int target) {
        int count = 0;
        for (int num : arr) {
            if (num == target) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4, 4, 5};
        int target = 2;
        System.out.println("Occurrences of " + target + ": " + countOccurrences(arr, target));
    }
}

C++实现

#include <iostream>
#include <vector>

int countOccurrences(const std::vector<int>& arr, int target) {
    int count = 0;
    for (int num : arr) {
        if (num == target) {
            count++;
        }
    }
    return count;
}

int main() {
    std::vector<int> arr = {1, 2, 2, 2, 3, 4, 4, 5};
    int target = 2;
    std::cout << "Occurrences of " << target << ": " << countOccurrences(arr, target) << std::endl;
    return 0;
}

优缺点

• 优点：实现简单，代码易于理解。
• 缺点：效率较低，尤其是当数组很大时。

方法二：二分查找法

算法思路

由于数组是排序的，我们可以利用二分查找来优化搜索过程。具体步骤如下：

1. 使用二分查找找到目标数字的第一次出现的位置（first）。
2. 使用二分查找找到目标数字的最后一次出现的位置（last）。
3. 计算出现次数：last - first + 1。

时间复杂度

• 最坏情况：O(log n)，因为二分查找的时间复杂度是对数级的。
• 最好情况：O(log n)。

Java实现

public class BinarySearch {
    public static int findFirstOccurrence(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                right = mid - 1; // 继续在左半部分查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    public static int findLastOccurrence(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                left = mid + 1; // 继续在右半部分查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    public static int countOccurrences(int[] arr, int target) {
        int first = findFirstOccurrence(arr, target);
        if (first == -1) {
            return 0;
        }
        int last = findLastOccurrence(arr, target);
        return last - first + 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4, 4, 5};
        int target = 2;
        System.out.println("Occurrences of " + target + ": " + countOccurrences(arr, target));
    }
}

C++实现

#include <iostream>
#include <vector>

int findFirstOccurrence(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // 继续在左半部分查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int findLastOccurrence(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1; // 继续在右半部分查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int countOccurrences(const std::vector<int>& arr, int target) {
    int first = findFirstOccurrence(arr, target);
    if (first == -1) {
        return 0;
    }
    int last = findLastOccurrence(arr, target);
    return last - first + 1;
}

int main() {
    std::vector<int> arr = {1, 2, 2, 2, 3, 4, 4, 5};
    int target = 2;
    std::cout << "Occurrences of " << target << ": " << countOccurrences(arr, target) << std::endl;
    return 0;
}

优缺点

• 优点：效率高，适合大规模数据。
• 缺点：实现稍复杂，需要理解二分查找的变种。

方法三：库函数法（可选）

某些语言提供了内置函数来简化操作。例如：

Java中的Arrays.binarySearch

import java.util.Arrays;

public class LibraryFunction {
    public static int countOccurrences(int[] arr, int target) {
        int first = Arrays.binarySearch(arr, target);
        if (first < 0) {
            return 0;
        }
        int last = first;
        while (last < arr.length && arr[last] == target) {
            last++;
        }
        while (first >= 0 && arr[first] == target) {
            first--;
        }
        return last - first - 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4, 4, 5};
        int target = 2;
        System.out.println("Occurrences of " + target + ": " + countOccurrences(arr, target));
    }
}

C++中的std::equal_range

#include <iostream>
#include <vector>
#include <algorithm>

int countOccurrences(const std::vector<int>& arr, int target) {
    auto bounds = std::equal_range(arr.begin(), arr.end(), target);
    return bounds.second - bounds.first;
}

int main() {
    std::vector<int> arr = {1, 2, 2, 2, 3, 4, 4, 5};
    int target = 2;
    std::cout << "Occurrences of " << target << ": " << countOccurrences(arr, target) << std::endl;
    return 0;
}

优缺点

• 优点：代码简洁，易于维护。
• 缺点：依赖语言特性，可能不适用于所有场景。

性能对比

结论

• 对于小规模数据或简单需求，线性搜索法足够且易于实现。
• 对于大规模数据或对性能有要求的场景，二分查找法是最佳选择。
• 如果语言支持，库函数法可以提供简洁高效的解决方案。

希望本文能帮助你在Java和C++中高效地解决排序数组中数字出现次数的问题！ “`