[LeetCode] Find the Duplicate Number

MoAir 發(fā)布于2019-08-15 15:53 / 2477人閱讀

Problem

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.

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

Solution

class Solution {
    public int findDuplicate(int[] nums) {
        int start = 0, end = nums.length-1;
        while (start <= end) {
            int mid = start + (end-start)/2;
            if (count(nums, mid) <= mid) {
                start = mid+1; //numbers no larger than mid <= mid, so mid is safe, search second half
            } else end = mid-1; //numbers less than mid > mid, so there is duplicate in first half
        }
        return start; //when start > end, 
    }
    private int count(int[] nums, int k) {
        int count = 0;
        for (int num: nums) {
            if (num <= k) count++;
        }
        return count;
    }
}

GPU云服務(wù)器云服務(wù)器 DUPLICATE the LeetCode sdp for the webrtc

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/69307.html

相關(guān)文章

LeetCode[287] Find the Duplicate Number

摘要：復(fù)雜度思路每次通過二分法找到一個值之后，搜索整個數(shù)組，觀察小于等于這個數(shù)的個數(shù)?？紤]，小于這個位置的數(shù)的個數(shù)應(yīng)該是小于等于這個位置的。要做的就是像找中的環(huán)一樣，考慮重復(fù)的點在哪里?？紤]用快慢指針。代碼把一個指針放回到開頭的地方 LeetCode[287] Find the Duplicate Number Given an array nums containing n + 1 in...

canopus4u 2019-08-14 15:03 評論0 收藏0
[LeetCode] 287. Find the Duplicate Number

Problem 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 nu...

rickchen 2019-08-16 14:25 評論0 收藏0
[Leetcode] Find the Duplicate Number 找到重復(fù)數(shù)字

摘要：暴力法復(fù)雜度時間空間思路如果不用空間的話，最直接的方法就是選擇一個數(shù)，然后再遍歷整個數(shù)組看是否有跟這個數(shù)相同的數(shù)就行了。二分法復(fù)雜度時間空間思路實際上，我們可以根據(jù)抽屜原理簡化剛才的暴力法。 Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is bet...

chnmagnus 2019-08-14 12:39 評論0 收藏0
[LeetCode] 609. Find Duplicate File in System

Problem Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms o...

sf190404 2019-08-19 11:11 評論0 收藏0
leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0