287. Find the Duplicate Number

LeetCode medium original: C# #array #backtracking #csharp #leetcode #math #medium #search
Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.
LeetCode Static

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

В arrayе есть только одно повторяющееся number, return это повторяющееся number.

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

Esempio:

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

Output: 2

C# soluzione

abbinato/originale 
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++ soluzione

bozza automatica, rivedere prima dell'invio 
#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 soluzione

abbinato/originale 
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 soluzione

abbinato/originale 
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 soluzione

abbinato/originale 
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 soluzione

abbinato/originale 
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
}

Algorithm

Definizione дубликата:

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

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

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

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

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

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte
Non ci sono ancora offerte attive.