@@ -0,0 +1,2115 @@
+//  Copyright 2016 The Sawdust Open Source Project%0A//%0A// Licensed under the Apache License, Version 2.0 (the %22License%22);%0A// you may not use this file except in compliance with the License.%0A// You may obtain a copy of the License at%0A//%0A//     http://www.apache.org/licenses/LICENSE-2.0%0A//%0A// Unless required by applicable law or agreed to in writing, software%0A// distributed under the License is distributed on an %22AS IS%22 BASIS,%0A// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A// See the License for the specific language governing permissions and%0A// limitations under the License.%0A//%0A%0Apackage array.duplicated;%0A%0A/**%0A * %3Cpre%3E%0A * Difficulty: Hard%0A * Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.%0A *%0A * Note:%0A *     a   You must not modify the array (assume the array is read only).%0A *     b   You must use only constant, O(1) extra space.%0A *     c   Your runtime complexity should be less than O(n2).%0A *     d   There is only one duplicate number in the array, but it could be repeated more than once.%0A *%0A * Tags:%0A *      Binary Search%0A *      Array%0A *      Two Pointers%0A * Similar Problems%0A *      (H) First Missing Positive%0A *      (M) Single Number%0A *      (M) Linked List Cycle II%0A *      (M) Missing Number%0A *%0A *%0A * Ideas:%0A *    a =%3E or array as index and check sign is not allowed%0A *    b =%3E can use array as index and check times%0A *    d =%3E xor cannot work.%0A *%0A *  Notes:%0A *    1  times length is nums.length%0A *    2  return -1 is no meaning but need this line%0A *%0A *  @see %3Ca href=%22https://leetcode.com/problems/find-the-duplicate-number/%22 %3E leetcoce%3C/a%3E%0A */%0Apublic class Leetcode287FindtheDuplicateNumber %7B%0A    public int findDuplicate(int%5B%5D nums) %7B%0A        int%5B%5D times = new int%5Bnums.length%5D;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            int v = nums%5Bi%5D;%0A            if (times%5Bv%5D != 0) %7B%0A                return v;%0A            %7D%0A            times%5Bv%5D++;%0A        %7D%0A        return -1;%0A    %7D%0A%7D%0A

Leetcode 287 Find the Duplicate Number