287. Find the Duplicate Number

leetcode medium

#array#backtracking#csharp#leetcode#math#medium#search

Task

Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.

В массиве есть только одно повторяющееся число, верните это повторяющееся число.

Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.

Пример:

Input: nums = [1,3,4,2,2]

Output: 2

C# solution

matched/original

public class Solution {
    public int FindDuplicate(int[] nums) {
        int duplicate = -1;
        for (int i = 0; i < nums.Length; i++) {
            int cur = Math.Abs(nums[i]);
            if (nums[cur] < 0) {
                duplicate = cur;
                break;
            }
            nums[cur] *= -1;
        }
        for (int i = 0; i < nums.Length; i++) {
            nums[i] = Math.Abs(nums[i]);
        }
        return duplicate;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindDuplicate(vector<int>& nums) {
        int duplicate = -1;
        for (int i = 0; i < nums.size(); i++) {
            int cur = abs(nums[i]);
            if (nums[cur] < 0) {
                duplicate = cur;
                break;
            }
            nums[cur] *= -1;
        }
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = abs(nums[i]);
        }
        return duplicate;
    }
}

Java solution

matched/original

class Solution {
    public int findDuplicate(int[] nums) {
        int duplicate = -1;
        
        for (int i = 0; i < nums.length; i++) {
            int cur = Math.abs(nums[i]);
            if (nums[cur] < 0) {
                duplicate = cur;
                break;
            }
            nums[cur] *= -1;
        }
        
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Math.abs(nums[i]);
        }
        return duplicate;
    }
}

JavaScript solution

matched/original

var findDuplicate = function(nums) {
    let duplicate = -1
    for (let i = 0; i < nums.length; i++) {
        let cur = Math.abs(nums[i])
        if (nums[cur] < 0) {
            duplicate = cur
            break
        }
        nums[cur] *= -1
    }
    for (let i = 0; i < nums.length; i++) {
        nums[i] = Math.abs(nums[i])
    }
    return duplicate
}

Python solution

matched/original

class Solution:
    def findDuplicate(self, nums):
        duplicate = -1
        for i in range(len(nums)):
            cur = abs(nums[i])
            if nums[cur] < 0:
                duplicate = cur
                break
            nums[cur] *= -1
        for i in range(len(nums)):
            nums[i] = abs(nums[i])
        return duplicate

Go solution

matched/original

func findDuplicate(nums []int) int {
    duplicate := -1
    for i := 0; i < len(nums); i++ {
        cur := abs(nums[i])
        if nums[cur] < 0 {
            duplicate = cur
            break
        }
        nums[cur] *= -1
    }
    for i := 0; i < len(nums); i++ {
        nums[i] = abs(nums[i])
    }
    return duplicate
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Explanation

Algorithm

Определение дубликата:

Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.

Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.

Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.

Восстановление массива:

Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива.

Возврат результата:

Верните найденный дубликат.

😎