Loading... <h1 id="toc_0">题目</h1> <p>给定一个长度为 n+1 的数组<code>nums</code>，数组中所有的数均在 1∼n 的范围内，其中 n≥1。</p> <p>请找出数组中任意一个重复的数，但不能修改输入的数组。</p> <h3 id="toc_1"><strong>样例</strong></h3> <pre><code class="language-cpp">给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。 返回 2 或 3。 </code></pre> <p><strong>思考题</strong>：如果只能使用 O(1) 的额外空间，该怎么做呢？</p> <h2 id="toc_2">思路</h2> <p>将区间范围 [1,n] 进行二分，遍历数组，计算数组元素位于两个区间的数量，如果元素数量大于区间长度，则代表重复元素在此区间，不停迭代。</p> <blockquote> <p>一分为二，每边至少有一边数字个数是大于坑的数量，找出来再一分为二，划分 <code>logn</code> 次</p> </blockquote> <p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-eeeda6f3d874bb2d602e015e4e7f0b1432" aria-expanded="true"><div class="accordion-toggle"><span>参考答案</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-eeeda6f3d874bb2d602e015e4e7f0b1432" class="collapse collapse-content"> </p> <pre><code class="language-cpp">class Solution { public: int duplicateInArray(vector<int> &nums) { // 对取值区间进行二分 int l = 1, r = nums.size() - 1; while (l < r) { int mid = l + (r - l) / 2; int sum = 0; for (auto x : nums) // 此处要 加= // 同时是元素与区间大小对比 if (x >= l && x <= mid) sum++; if (sum > mid - l + 1) r = mid; else l = mid + 1; } return r; } }; </code></pre> <p><div style="height: 15px"></div></div></div></div></p> 最后修改：2021 年 05 月 12 日 11 : 37 AM © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付