← Static tasks

540. Single Element in a Sorted Array

leetcode medium

#array#csharp#leetcode#medium#sort

Task

Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз.

Верните единственный элемент, который встречается только один раз.

C# solution

matched/original
class Solution {
    public int SingleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[^1];
    }
}

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 int SingleNonDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[^1];
    }
}

Java solution

matched/original
class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}

JavaScript solution

matched/original
class Solution {
    singleNonDuplicate(nums) {
        for (let i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] !== nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}

Python solution

matched/original
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        for i in range(0, len(nums) - 1, 2):
            if nums[i] != nums[i + 1]:
                return nums[i]
        return nums[-1]

Go solution

matched/original
func singleNonDuplicate(nums []int) int {
    low, high := 0, len(nums)-1

    for low < high {
        mid := low + (high-low)/2
        if mid%2 == 1 {
            mid-- // всегда проверяем пары с чётного индекса
        }
        if nums[mid] == nums[mid+1] {
            low = mid + 2
        } else {
            high = mid
        }
    }

    return nums[low]
}

Explanation