面试题目的算法解决

Interview Questions

整型数组，只有一组数出现奇数次，其他数都出现偶数次，怎么找到出现奇数次的数

a ^ a的结果为0，而0 ^ a的结果为a。也就是说，如果一个数在数组中出现偶数次，那么将数组中的所有数进行异或运算，最终结果为0；而如果一个数出现奇数次，那么最终结果就是这个数本身。

C语言

#include <stdio.h>
int FindOdd(int arr[], int size)
{
    int eor = 0;
    for (int i = 0; i < size; i++)
    {
        eor ^= arr[i];
    }
    return eor;
}

int main()
{
    int arr[] = {2, 4, 6, 2, 4, 8, 6}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]);

    int OddN = FindOdd(arr, size);
    printf("出现奇数次的是: %d\n", OddN);

    return 0;
}

python

def Find_Odd_Occuring_number(arr):
    eor = 0
    for i in arr:
        eor ^= i
    return eor


arr = [2, 4, 6, 2, 4, 8, 6]
odd_numbers = Find_Odd_Occuring_number(arr)
print(f"出现奇数次的数是: {odd_numbers}")

整型数组，有两组数出现奇数次，其他数都出现偶数次，怎么找到出现奇数次的数

C语言

#include "stdio.h"

int FindOdd(int arr[], int size)
{
    int eor = 0;
    for (int i = 0; i < size; i++)
    {
        eor ^= arr[i];
    }

    int rightone = eor & (~eor + 1);
    int num1 = 0;
    int num2 = 0;

    for (int j = 0; j < size; j++)
    {
        if ((arr[j] & rightone) == 0)
        {
            num1 ^= arr[j];
        }
        else
        {
            num2 ^= arr[j];
        }
    }

    return (num1 << 16) | num2;
}

int main()
{
    int arr[] = {2, 4, 6, 2, 4, 8, 6, 5}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]);

    int result = FindOdd(arr, size);
    int num1 = (result >> 16) & 0xFFFF;
    int num2 = result & 0xFFFF;

    printf("The numbers occurring odd number of times are: %d and %d\n", num1, num2);
    return 0;
}

python

def Find_Odd_Occuring_number(arr):
    eor = 0
    for i in arr:
        eor ^= i
    rightone = eor & (~eor + 1)
    eor2 = 0
    eor3 = 0

    for j in arr:
        if j & rightone:
            eor2 ^= j
        else:
            eor3 ^= j

    return eor2, eor3


arr = [2, 4, 6, 2, 4, 8, 6, 5]
odd_numbers = Find_Odd_Occuring_number(arr)
print(f"出现奇数次的数是: {odd_numbers}")

插入算法Insertion_sort

python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


# 从键盘输入待排序的列表
input_str = input("请输入待排序的列表（以空格分隔）：")
arr = list(map(int, input_str.split()))

# 调用插入排序算法
insertion_sort(arr)

# 输出排序后的列表
print("排序后的列表：", arr)