数组在另一个数组中没有出现的元素

求一个数组在另一个数组中没有出现的元素
例如 求int a[]数组某个元素在int b[]中没有出现
int a[]={1,3,0,4,2};
int b[]={1,2,3,4,5};
应该最后输出是： 0

求思路~~~~~~

[解决办法]
hash!!
[解决办法]
hash能够帮你解决这个问题！！
[解决办法]
先求两数组交集，再原数组中扣除交集部分就能得到结果！
[解决办法]
如果 b[] 是整数数组,且b[]的范围不大,即 max(b)-min(b) 是一个已知的常数,则可以这样做:
STEP1: 设置整数数组 c[], 其个数就是 max(b)-min(b)+1, 令其初值为 0;
STEP2: for (i=0;i<b 元素个数;i++)
 STEP2.1: c[b[i]-min(b)]=1;
STEP3: for (i=0;i<a 元素个数;i++)
STEP3.1 if (c[a[i]==0) 输出 a[i] 不在 b 中;
该算法耗时O(n),假设 max(b)-min(b)+1 是常数.

如果 b[] 不是整数,或 b[] 的范围太大,则:
STEP1: 将 b[] 排序,该步耗时 O(nlogn);
STEP2: for (i=0;i<a 的元素个数;i++)
STEP2.1: 在 b[] 中用二分法查找 a[i];
STEP2.2: 如果没有找到,输出 a[i] 不在b[] 中;
该算法耗时 O(nlogn)

[解决办法]

Java code

package CSDN;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * 输出数组a中不在数组b中出现的元素 * @author xqh * */public class ArrayFindNum {    public static void main(String[] args) {        int[] a = { 1, 3, 0, 4, 2 }; //数组a        int[] b = { 1, 2, 3, 4, 5 }; //数组b        List<Integer> list = new ArrayList<Integer>(); //数列        Arrays.sort(b); //对数组b排序        for (int i = 0; i < a.length; i++) {            if (!binarySearch(b, a[i])) // 采用二分查找法判断数组a中的元素是否出于在数组b中                list.add(a[i]); // 数列存放不出现在数组b中的元素        }        System.out.println("数组a中不在数组b中出现的元素:");        for (int i : list)            System.out.print(i + " ");    }    /**     * 二分查找法     * @param arr 数组     * @param num 数值     * @return 找到则返回true,否则返回false     */    private static boolean binarySearch(int[] arr, int num) {        int low = 0;        int high = arr.length - 1;        while (low <= high) {            int middle = (low + high) / 2;            if (arr[middle] == num) {                return true;            } else if (arr[middle] > num) {                high = middle - 1;            } else                low = middle + 1;        }        return false;    }}
[解决办法]
探讨

楼主可以参考一下 ，这个写法，思路很简单，用二分查找法来判断数组a中的元素是否存在于数组b中

[解决办法]
把2个数组都排好序
然后2指针分别从2个数组头开始扫描
相同就去掉，2指针均后移一位
不同就把数小的那个指针后移一位

[解决办法]
方法一：直接暴力法。对数组a中的每一个元素，遍历一遍数组b，看数组a的元素是否在数组b里面
方法二：将数组b里面的元素放到一个hash表里面，然后就可以直接对a的元素hash一下就可以得知是否在b里面
方法三：如果b的元素比较集中，例如是[1~10]的话则可以用一个10位的位图，假设b里面有1，3，5，7，9的话则该位图的值为1010101010（即在b里面的话对应位为1，否则为0）。这样的话对数组a里面的每个元素，假设为i的话则直接看位图的第i位是否为0，是的话则可以得知i在数组b中出现
[解决办法]
顶10楼位图法
Java code
public class bitmap{    int block = 4*8;   //sizeof(int)    int[] map;        public bitmap(int upperBoundary){        int k = 1;        upperBoundary /= block;        while(upperBoundary != 0){            k++;            upperBoundary/=2;        }        map = new int[k];    }        //将指定位设为1    public void set(int position){        int i = position/block;        int j = position%block;        int temp = 1 << j;        map[i] = map[i]|temp;    }        //返回指定位的值    public int check(int position){        int i = position/block;        int j = position%block;        int temp = 1 << j;        temp = temp&map[i];        temp = temp >>> j;        return temp;    }        public void print(){        System.out.println("map.length = "+map.length);        for (int i = 0; i < map.length; i++)             System.out.println("map."+i+": "+Integer.toHexString(map[i]));    }        public static void main(String[] args){        int a[]={1,3,0,4,2,31,32};        int b[]={1,2,3,4,5,31,32};                //用位图记录b中元素        bitmap m = new bitmap(50);    //假设数值上限是50            for (int i = 0; i < b.length; i++){            m.set(b[i]);        }                m.print();                //检查a中b没有的元素并输出        for (int i = 0; i < a.length; i++){            if (m.check(a[i]) == 0) System.out.println(a[i]);        }    }} 
 
[解决办法]
C/C++ code
/*    数组C中存放了满足条件的值    */void find (A[], sizeA, B[], sizeB, C[]){    int i, j, k ;    /*    将A和B分别按非递减顺序排序    */    /*    O(sizeAlgsizeA) and O(sizeBblgsizeB)    */    Sort A and B ;    i = j = k = 0 ;    /*    O (sizeA)的遍历    */    while (i < sizeA && j < sizeB)    {        while (i < sizeA && j < sizeB && A[i] < B[j])        {            i++ ;            C[k++] = A[i] ;        }        while (i < sizeA && j < sizeB A[i] > B[j])            j++ ;        i++ ;        j++ ;    }    while (i < sizeA)        C[k++] = A[i++] ;}
[解决办法]
上面的方法都很好,领教了.
[解决办法]
这也就是匹配问题吧
用kmp算法看看
[解决办法]
顶8楼
当初也是用这个方法算的。

复杂度为O(n)？
[解决办法]
嘿嘿，正在学习C#的linq，练手
  private void TestLinq()  
       {
           int[] a = new int[] {1,3,0,4,2 };
           int[] b = new int[] { 1,2,3,4,5};
           var q = (from c in a select c).Except(from d in b select d);
           foreach (int i in q) { Console.Write("{0} ", i); }
          
           Console.WriteLine();
           Console.ReadKey();
       }
[解决办法]
学习位图法
[解决办法]
探讨

采用位图
1、将a中的每个元素都占一个位，即设置为1
2、将b中的每个元素，和位图中的各位进行&amp;运算，结果为0的说明没有

[解决办法]
C# code
int[] a = new int[] { 1, 3, 0, 4, 2 };int[] b = new int[] { 1, 2, 3, 4, 5 };var result = a.Except(b);