Javaの問題を解決する方法

導入

我々は行方不明の要素を見つけるのXOR原理を使用します.
XOR演算子を使用してこれを実現する方法を見てみましょう.

問題声明

配列nums 含むn 範囲内の異なる数[0, n] , 配列から見つからない範囲の唯一の数値を返します.

Input: nums = { 9, 6, 4, 2, 3, 5, 7, 0, 1 }

Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

制約

それは線形複雑さで行う.

n == nums.length

ヒント:算術の進行を使用して、ブルートフォースアプローチで移動します.次に最適化します.

解決策

アプローチ01：ハッシュテーブル

これは、私たちが一度すべての要素を繰り返しているように、上記のものより良いですO(n) 余分なメモリスペース.

アルゴリズム

このアルゴリズムは、まず第1の要素の各々を挿入する以外は、ブルートフォースアプローチとほとんど同じであるnums にSet , 私たちが後で封じ込めについての問い合わせを許すO(1) 時間.

コード

import java.util.HashSet;

class MissingNumber {
    private static int helper(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();

        for (int num : nums) {
            set.add(num);
        }

        int n = nums.length + 1;

        for (int i = 0; i < n; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

複雑性解析

時間の複雑さO(n) , forループの時間複雑さはO(n) そして、ハッシュテーブルオペレーションaddO(1) .
空間の複雑さO(n) , ハッシュテーブルによって必要とされるスペースは、nums .

アプローチ01：数学

これはコンセプトについてn 自然数

アルゴリズム

我々の合計を知っているn 自然数は[n(n+1)/2]​

さて、与えられた配列要素の実際の和とn 自然数は、私たちに不足している数を与えます.

コード

class MissingNumber {
    private static int helper(int[] nums) {
        int n = nums.length;
        int expectedSum = ((n * (n + 1)) / 2);

        int actualSum = 0;

        for (int num : nums) {
            actualSum += num;
        }

        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

複雑性解析

時間の複雑さO(n) , forループの時間複雑さはO(n) .
空間の複雑さO(1) , 我々は余分なスペースを使用していないとして.

コーディング演習

まず、これらのコードスニペットを詳しく見て、解決策を考えてみましょう.
あなたの解決策は^ 演算子.
この問題はあなたの練習のために設計されているので、最初にそれを解決しようとする.あなたが立ち往生する場合は、ソリューションのセクションで提供されるソリューションを常に参照することができます.グッドラック!

class Solution{
    public static int missingNumber(int[] nums){
       // Write - Your - Code- Here

        return -1; // change this, return missing element; if none, return -1
    }
}

以下に解決策を説明する.

We solved the problem using lookup (Memoization/Hashtable) and using the mathematical formula for the sum of n natural numbers, Let's solve this more efficiently using bit-level operations with ^ or xor.

ソリューションレビュー：ビット操作

私たちはビット操作を扱っていて、ビットごとのオペレーターでこれらの問題の全てを解決したいです.

コンセプト

我々がXORをとるならば0 とbit , それはbit .

a ^ 0 = a

我々が2つの同じビットのXORを取るならば、それは帰ります0 .

a ^ a = 0

For n 数、下の数学を適用することができます.

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b;

例えば、

1 ^ 5 ^ 1 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5;

それで、我々はユニークな数を見つけるために一緒にすべてのビットをXORすることができます.

アルゴリズム

変数を初期化します.res = 0 .

配列要素を繰り返します0 to length + 1 アンド^ 上記の初期化変数を持つ.

すべての要素を反復処理し、変数に値を格納します.

コード

ここでは、このソリューションのロジックです.

class MissingNumber {
    private static int helper(int[] nums) {
        int n = nums.length + 1;
        int res = 0;

        for (int i = 0; i < n; i++) {
            res ^= i;
        }

        for (int value : nums) {
            res ^= value;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

複雑性解析

時間の複雑さO(n) , 私たちは2つの独立したループを使用しています.だから時間=O(n) + O(n) => O(n) .
どこn は、すべての要素を反復処理する必要があるため、配列内の要素数です.だから、最高の最悪の時間はO(n) .
空間の複雑さO(1) , 空間の複雑さはO(1) . 余計なスペースは割り当てられません.

最適化

最後の解決策を最適化しましょう.
我々は、行方不明の数を見つけるために2つの独立したループを使用しています.
さあ、ループのシングルにしましょう.100万整数の配列があれば、200万の操作を行います.
操作の数を減らすことができますn , どこn が配列のサイズです.
下のコードを見てみましょう.

class MissingNumber {
    private static int helper(int[] nums) {
        int missing = nums.length;

        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

ここで、コードは上のものより少ない線を持っています.

複雑性解析

時間の複雑さO(n) : どこn すべての要素を反復処理する必要があります.だから、最高の、最悪の時間はO(N) .
空間の複雑さO(1) , スペースの複雑さはo(1)であり、余分なスペースは割り当てられない.

ビットトリックをマスターに興味がありますか？

我々は200 k以上のプログラマに愛されているコースを持っている.コースへのリンク:コーディングインタビューのためのマスタービット操作.
このコースでは、私たちはどのように問題を解決するためのビット操作を使用して、あなたのアルゴリズムと問題解決能力を最適化するために使用することができます強力なテクニックを学びます.コースはスケッチ、詳細なステップバイステップの図面、およびビット演算子を使用してそれを解決するために様々な方法で簡単な説明をしています.
これらのビットトリックは、O(1)時間で主にアルゴリズムを実行する際に、競争上のプログラミングとコーディングインタビューに役立つことができました.
誰かがファング(フェイスブック、アマゾン、アップル、Netflix、およびGoogle)のためのコーディングをコーディングする準備を始めるとき、これは最も重要な/重要な話題のうちの1つです.
物事をキックするために、我々は数システムについて学ぶことによって開始されますどのように表現されます.そして、6つの異なるビットごと演算子について学びます.全体を通して、私たちの経験の経験を通じて手の経験のトンを得る私たちの理解を高めるために.
このコースを完了した後、我々はより効率的に問題を解決することができます!🤩