0 0 vote
Article Rating
Subscribe
提醒
guest
5 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
sunznx
// CreateTime: 2021-01-19 01:48:29
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1;
        int r = nums.size();


        while (l < r) {
            int m = (l+r) / 2;
            if (check(nums, m)) {
                r = m;
            } else {
                l = m+1;
            }
        }
        return (int)(l);
    }


    bool check(vector<int> &nums, int x) {
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= x) {
                count++;
            }
        }
        return count > x;
    }
};


暴走的楚狂

Python 有set解决这个问题太简单了,O(1)space的那个要求算法完全是需要学习定式
下面这个挺有趣的

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for index, num in enumerate(nums):
            while (nums[index] != nums[nums[index]-1]):
                nums[nums[index]-1], nums[index] = nums[index], nums[nums[index]-1]
        return nums[-1]

demo

public static int findDuplicate(int[] nums) {
        int[] temp = new int[nums.length]  ;
        int i  = 0 ;
        while (i < nums.length){
            temp[nums[i]] = temp[nums[i]] + 1 ;
            if (temp[nums[i]] == 2 ){
                return nums[i]  ;
            }
            i++ ;
        }
        return  0 ;
    }