2个无序数组相同元素的数量 算法

可以使用哈希表（Hash Table）来解决这个问题。

首先，创建一个哈希表，遍历第一个数组，将数组中的每个元素作为键（key），并将其值（value）设为1。接着，遍历第二个数组，对于每个元素，查找哈希表中是否存在该元素作为键的项，如果存在，则将该项的值加1，并将该元素从第二个数组中删除。最后，哈希表中所有键的值的总和就是两个数组中相同元素的数量。

下面是该算法的Python实现代码：

def count_same_elements(arr1, arr2):
    hash_table = {}
    count = 0
    for num in arr1:
        hash_table[num] = 1
    for num in arr2:
        if num in hash_table and hash_table[num] == 1:
            count += 1
            hash_table[num] = 0
    return count

该算法的时间复杂度为O(n)，其中n为两个数组中元素的总数。

相关问题

给定一个无序数组A[1..n],其中元素各不相同,n=2的k次幂。用伪代码实现分治算法

下面是一个用伪代码实现的分治算法，用于找到一个无序数组A中的最大值和最小值：

function find_max_min(A)
    n = length(A)
    if n == 1
        return A[1], A[1]
    else
        mid = n / 2
        max1, min1 = find_max_min(A[1:mid])
        max2, min2 = find_max_min(A[mid+1:n])
        max_val = max(max1, max2)
        min_val = min(min1, min2)
        return max_val, min_val

该算法首先检查数组A的大小。如果A的大小为1，则A中的唯一元素既是最大值也是最小值。否则，算法将数组A分成两个大小相等的子数组，并递归地找到每个子数组中的最大值和最小值。最后，算法将两个子数组的最大值和最小值进行比较，以找到整个数组A的最大值和最小值。

在该算法中，递归的基本情况是当数组A的大小为1时。递归的一般情况是将数组A分成两个大小相等的子数组，并递归地找到每个子数组中的最大值和最小值。最后，将两个子数组的最大值和最小值进行比较以找到整个数组A的最大值和最小值。在每个递归层次中，该算法执行常量次数的比较和赋值操作，因此，该算法的时间复杂度为O(nlogn)。

注意，在上面的伪代码实现中，子数组的索引从1开始，而不是从0开始。

java编写一个程序，实现二分查找算法，查找一个给定的整数是否在无序数组中。

要在无序数组中实现二分查找算法，我们需要先对数组进行排序，然后再进行二分查找。下面是一个使用二分查找算法在无序数组中查找给定整数的Java程序示例：

import java.util.Arrays;

public class BinarySearch {
    public static boolean binarySearch(int[] arr, int target) {
        Arrays.sort(arr); // 对数组进行排序
        
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return true; // 找到目标元素，返回true
            } else if (arr[mid] < target) {
                left = mid + 1; // 目标元素在右半部分，继续在右半部分查找
            } else {
                right = mid - 1; // 目标元素在左半部分，继续在左半部分查找
            }
        }

        return false; // 没有找到目标元素，返回false
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 3, 11, 7, 1};
        int target = 5;

        boolean result = binarySearch(arr, target);

        if (result) {
            System.out.println("目标元素在数组中");
        } else {
            System.out.println("目标元素不在数组中");
        }
    }
}

在上面的示例中，我们首先使用`Arrays.sort()`方法对无序数组`arr`进行排序。然后，我们使用与有序数组相同的二分查找算法来查找目标整数`target`。如果找到目标元素，则返回`true`，否则返回`false`。

在`main`方法中，我们创建一个无序数组`arr`和一个目标整数`target`，然后调用`binarySearch`方法进行查找，并根据返回结果输出相应的消息。

运行上述程序，将会输出：

目标元素在数组中

这表示目标元素5在无序数组中。请注意，在使用二分查找算法之前，我们需要先对无序数组进行排序。