<p>Given an integer array <code>nums</code>, return <code>true</code> if any value appears <strong>at least twice</strong> in the array, and return <code>false</code> if every element is distinct.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p>The element 1 occurs at the indices 0 and 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p>All elements are distinct.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1,3,3,4,3,2,4,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    bool b = false;
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() == 0){return false;}
        else if (nums.size() == 1){return false;}
        else if (nums.size() == 2)
        {
            if (nums[0] == nums[1]) {return true;}
            else {return false;}
        }

        for (int i = 1; i < nums.size(); i = i * 2)
        {
            for (int ls = 0; ls + i - 1 < nums.size() - 1; ls += i * 2)
            {
                int mid = min(ls + i - 1, nums.size() - 1);
                int re = min (ls + (i * 2) - 1, nums.size() - 1);

                merge(nums, ls, mid, re);

            }
        }
        return b;
    }

    void merge(std::vector<int>& nums, int ls, int mid, int re)
    {

        int las = mid - ls + 1;
        int ras = re - mid;

        int la[las];
        int ra[ras];
        int ni = ls;

        for (int i = 0; i < las; i++)
        {
            la[i] = nums[ni];
            ni++;
        }

        for (int i = 0; i < ras; i++)
        {
            ra[i] = nums[ni];
            ni++;
        }

        ni = ls;
        int lai = 0;
        int rai = 0;

        while (lai < las && rai < ras)
        {
            if (la[lai] == ra[rai])
            {b = true;}
            if (la[lai] < ra[rai])
            {
                nums[ni] = la[lai];
                lai++;
            }
            else
            {
                nums[ni] = ra[rai];
                rai++;
            }
            ni++;
        }

        while (lai < las)
        {
            nums[ni] = la[lai];
            lai++;
            ni++;
        }

        while (rai < ras)
        {
            nums[ni] = ra[rai];
            rai++;
            ni++;
        }
    }

    int min (int x, int y)
    {return (x < y)? x : y;}
};
60115