给出n个整数（每个整数均在int范围内），n为奇数，其中有且仅有一个数出现了奇数次，其余的数 都出现了偶数次。 找出出现了奇数次的那个数。

这是一个经典的哈希表（Hash Table）或者计数排序（Counting Sort）问题。给定一个数组，由于元素都是整数，并且出现次数有明显的奇偶性，我们可以利用这个特性快速找到那个唯一的奇数出现次数。

算法步骤大致如下：

1. 初始化一个大小为`max(int) + 1`的布尔数组（或哈希表）`count[]`，所有元素初始值设为0。这里假设输入的整数范围不大于`int`的最大值。

2. 遍历输入数组，对于每个元素`num`，更新`count[num]`的值，使其加一。遍历完成后，`count[]`数组的每个元素表示对应数字出现的次数。

3. 再次遍历`count[]`数组，查找第一个值为奇数的索引。这个索引对应的数字就是出现了奇数次的那个数。

def find_odd_occurrence(nums):
    count = [0] * (max(nums) + 1)
    for num in nums:
        count[num] += 1

    for i, val in enumerate(count):
        if val % 2 != 0:
            return i

# 示例
nums = [1, 2, 3, 4, 5, 1, 2, 3, 1]
print(find_odd_occurrence(nums))  # 输出：4，因为数4出现了奇数次(3次)

相关问题

给出n个整数，n为奇数。其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。 请找出出现了奇数次的那个整数。给出代码

这个问题可以通过哈希表（unordered_map）来解决。遍历数组，对于每个元素，检查其出现次数。如果当前元素已经在哈希表中，则减少它的计数；否则增加计数。因为只有一个是奇数次出现，所以当遇到第一个计数为奇数的元素时，就是我们要找的答案。

以下是C++代码实现：

#include <unordered_map>

int findSingle(int arr[], int n) {
    std::unordered_map<int, int> countMap;

    // 遍历数组，更新元素的出现次数
    for (int i = 0; i < n; i++) {
        countMap[arr[i]]++;
    }

    // 再次遍历数组，查找出现次数为奇数的元素
    for (int i = 0; i < n; i++) {
        if (countMap[arr[i]] % 2 == 1) {
            return arr[i];
        }
    }

    // 如果没有找到，返回-1 或者抛异常，这里假设找不到则返回-1
    return -1;
}

// 示例用法
int main() {
    int arr[] = {1, 2, 3, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = findSingle(arr, n);
    std::cout << "The number that appears odd times is: " << result << std::endl;
    return 0;
}

在这个代码中，`findSingle` 函数接受一个整数数组 `arr` 和长度 `n`，然后使用哈希表 `countMap` 存储每个元素及其出现次数。第一次遍历结束后，哈希表中的键值对表示了所有元素的出现次数。第二次遍历时，只要发现某个元素的计数是奇数，就立即返回这个元素。如果没有找到这样的元素，函数返回 -1（实际应用中可以根据需求修改返回值或处理方式）。

给定一个长度为n(0<n≤200)的正整数序列，按照以下要求排序： 奇数排在偶数前面； 奇数与偶数各自从小到大排列； 请根据以上要求完成排序，输出排序后的整数序列。 输入格式: 第一行给定一个整数n,第二行给出n个正整数，每个正整数不会超过int所能表示的范围。 输出格式: 输出排序后的整数序列，每行一个整数，共n行。,写出c语言代码

以下是 C 语言实现该题目的代码：

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void oddEvenSort(int arr[], int n) {
    int i, j, odd_idx;
    for (i = 0; i < n-1; i++) {
        odd_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] % 2 && arr[j] < arr[odd_idx])
                odd_idx = j;
        if (i != odd_idx)
            swap(&arr[i], &arr[odd_idx]);
    }
    for (i = 0; i < n-1; i++) {
        if (arr[i] % 2 == 0) {
            int min_idx = i;
            for (j = i+1; j < n; j++)
                if (arr[j] % 2 == 0 && arr[j] < arr[min_idx])
                    min_idx = j;
            if (i != min_idx)
                swap(&arr[i], &arr[min_idx]);
        }
    }
}

int main() {
    int n, i;
    scanf("%d", &n);
    int arr[n];
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    oddEvenSort(arr, n);
    for (i = 0; i < n; i++)
        printf("%d\n", arr[i]);
    return 0;
}

其中，`oddEvenSort()` 函数实现了奇数排在偶数前面并且奇数与偶数各自从小到大排列的排序算法。首先，它找到第一个奇数的位置，然后将其与当前位置交换；接着，它对剩下的偶数进行从小到大的选择排序。

时间复杂度为 O(n^2)，但由于数据规模较小，所以可以通过本题。