为了账号安全,请及时绑定邮箱和手机立即绑定

查找数组中唯一未配对的元素

查找数组中唯一未配对的元素

犯罪嫌疑人X 2019-11-13 14:09:19
埃森哲面试题:您已被给定尺寸的阵列2n+1具有n对整数(可以是+ve,-ve或0)和一个未配对的元件。您将如何找到未配对的元素?对表示重复。所以(3,3)是一对,(3,-3)而不是一对。
查看完整描述

3 回答

?
ITMISS

TA贡献1871条经验 获得超8个赞

采取XOR的所有元素。


对将取消为


a XOR a = 0

结果将是唯一不成对的元素,因为


0 XOR a = a

如果可以销毁数组,则可以XOR相邻元素。完成后,数组的最后一个元素具有未配对的元素:


N = Num of elements in array.

for( i=1 to N )

   arr[i] ^= arr[i-1];    

print arr[N-1]

如果无法销毁该数组,则可以使用变量保存结果:


N = Num of elements in array.

Unpaired = arr[0];

for( i=1 to N )

   Unpaired = Unpaired ^ arr[i];    

print Unpaired

C函数做同样的事情:


int findUnpaired(int *arr,int len) {

 int i;                  // loop counter.

 int unpaired;           // to hold the unpaired element.


 unpaired = arr[0];      // initialize it with the 1st array ele.


 for(i=1;i<len;i++) {    // loop for all remaining elements.

    unpaired ^= arr[i];  // XOR each element with the running XOR.

 }

 return unpaired;        // return result.

}


查看完整回答
反对 回复 2019-11-13
?
波斯汪

TA贡献1811条经验 获得超4个赞

具有XOR解决方案的单行Linq示例:


DotNetFiddle上的演示


public static void Main()

{

    int[] tab = { 1, 2, 3, 2, 1 };

    Console.WriteLine(GetSingle(tab));

}


private static int GetSingle(IEnumerable<int> tab)

{

    return tab.Aggregate(0, (current, i) => current ^ i);

}

为了乐趣和利润


编辑:


此代码段的说明。


var a = 2;

var b = 2;

Console.WriteLine(a ^ b); // will print 0

// because x ^ x == 0


var c = 3;

Console.WriteLine(a ^ b ^ c); // will print 3

// because 0 ^ x == x


Console.WriteLine(0 ^ a); // guess the output

// get it? :)

// Now, lets aggregate this enumerable ;)


查看完整回答
反对 回复 2019-11-13
?
天涯尽头无女友

TA贡献1831条经验 获得超9个赞

最好的答案是XOR运算符。只是为了好玩,如果允许对数组进行排序,可以对它进行排序并比较相邻的整数。假定所有整数恰好出现两次,一个整数出现一次。


// Random array of integers

int[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9};


// Sort the array.

Arrays.sort(arr);


// Array now looks like: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 

// Cycle through array comparing adjacent values.

for(int i = 0; i < arr.length; i++){


    // This would mean the single number was the last element in the array.

    if(i == arr.length-1)

        singleNum = arr[i];


    // If the adjacent elements are the same, skip foward. 

    if(i < arr.length-1 && arr[i] == arr[i+1])

        i ++;

    else

        // Otherwise, you found the single number.

        singleNum = arr[i];

}


查看完整回答
反对 回复 2019-11-13
  • 3 回答
  • 0 关注
  • 605 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信