如何改进代码以返回不成对的元素

Question

我正在为即将到来的编码面试练习,这是我的一个练习题,也是我离我有多远.

我该如何改进该计划以及您的建议.

此外,是否有任何城市可以帮助提高我的编码技能.

题;

    A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

    For example, in array A such that:

      A[0] = 9  A[1] = 3  A[2] = 9
      A[3] = 3  A[4] = 9  A[5] = 7
      A[6] = 9
    the elements at indexes 0 and 2 have value 9,
    the elements at indexes 1 and 3 have value 3,
    the elements at indexes 4 and 6 have value 9,
    the element at index 5 has value 7 and is unpaired.
    Write a function:

    class Solution { public int solution(int[] A); }

在给定由满足上述条件的N个整数组成的数组A的情况下,返回未配对元素的值.

    For example, given array A such that:

      A[0] = 9  A[1] = 3  A[2] = 9
      A[3] = 3  A[4] = 9  A[5] = 7
      A[6] = 9
    the function should return 7, as explained in the example above.

    Assume that:

    N is an odd integer within the range [1..1,000,000];
    each element of array A is an integer within the range [1..1,000,000,000];
    all but one of the values in A occur an even number of times.
    Complexity:

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
    Elements of input arrays can be modified.


Solution;

import java.util.*;

public class Solution {
    public int solution(int[] A) {
            int x;

        for(int i = 0; i < 7; i++)
        {
             //create an integer array containing an odd number of elements of numbers ranging from 1 - 1,000,000

//for(int N = 1; N <= 1,000,000; N++)

            int N = 1;

            while(N > 1 && N <= 1000000)
            {

                //check if N is odd then assign to the array               

                if(N != N/2)
                {
                    A[i] = N;
                }
            }

            //check for any element not paired more than once

            if(A[i] != A[i++])
            {
                x = A[i];
            }
            else 
                return 0;
        }

        //return unpaired elemnent
        return x;
    }
}

Answer 1

接受的解决方案违反了要求:

预期的最坏情况时间复杂度是O(N)

因为它具有二次复杂度(两个嵌套循环).一个明显的快速解决方案是使用a HashSet<Integer>来记住尚未配对的数字.但这会违反其他要求:

预期的最坏情况空间复杂度为O(1)

有一个简单的技巧满足两者:

public int solution(int[] A) {
    int result = 0;
    for (int x : A) result ^= x;
    return result;
}

这使用了这个事实,即x ^ x == 0任何x和相关性^.这意味着任何一对相等的值都会被取消,剩下的是单个不成对的值(在多个不成对的值的情况下,结果没有意义;无法检测到这种情况).

米肯诺接受的解决方案是错误的.对于输入,{1, 1, 1}有一对和一对未配对,所以结果应该是1,但它返回0.

Answer 2

这个答案在 Codility 上进行了测试，并且在性能和正确性方面获得了 100% 的成绩。

我正在做的是：

1. 对数组进行排序，使对组合在一起，因此我将能够通过遍历数组来检查数组中的每两对。

2. 然后我将 2 添加到两个索引以获得下一对，依此类推。

3. 第一个不匹配意味着我们得到了我们的目标，因为两个索引指向对。

这是代码：

public static int solution (int[] x) {
    int found = 0;
    int i = 0;
    int j = 1;

    Arrays.sort(x);
    //To sort the array so if you have {9 , 3 , 9 , 3 , 9 , 7 , 9} 
    //it will be { 3 , 3 , 7 , 9 , 9 , 9 , 9}
    if (x.length == 1) {
        found = x[0];
    }

    while (x.length % 2 == 1 && i < x.length && j < x.length) {
        if (x[i] == x[i+1]) {
            i = i + 2;
            j = j + 2;  
        } else {
            found = x[i];
            break;
        }
    }

    if (found == 0 && i == x.length-1) {
        found = x[i];
    }

    return found;
}