freeCodeCamp 每日编程挑战解析：Challenge 276「Offending Element」乱序元素定位算法

freeCodeCamp 每日编程挑战解析：Challenge 276「Offending Element」乱序元素定位算法

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp

freeCodeCamp 的每日编程挑战（Daily Coding Challenges）系列以一天一道题的方式，帮助学习者系统训练算法与数据结构基本功。本篇以 JavaScript 区块中的Challenge 276: Offending Element为例，完整还原题目描述、全部测试用例与官方参考解答，并从源码层面梳理这道题在 freeCodeCamp 仓库中从 Markdown 课程文件、GraphQL 种子数据到 MongoDB 集合与公开 API 端点的完整链路。读完本文，你既能掌握「从近乎有序数组中定位唯一乱序元素」这类题型的通用解法与边界处理，也能理解这类题目是如何被生产系统化地发布与供题的。

挑战背景：daily-coding-challenges 区块

这道题位于 freeCodeCamp 课程体系的每日编程挑战区块中，其 Markdown 源文件为 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69e2383af7832c8032603b92.md，文件头部的 Frontmatter 记录了以下元数据：

id: 69e2383af7832c8032603b92 title: "Challenge 276: Offending Element" challengeType: 28 dashedName: challenge-276

其中challengeType: 28表示这是一种代码编程类挑战。从区块结构配置 curriculum/structure/blocks/daily-coding-challenges-javascript.json 可以看到，该区块还启用了以下特性：

• usesMultifileEditor: true：使用多文件编辑器作答；
• disableLoopProtectTests: true：关闭循环保护相关的测试注入；
• blockLayout: "legacy-challenge-list"：区块以传统挑战列表形式展示；
• isUpcomingChange: true：标记为即将上线的新特性；
• helpCategory: "JavaScript"：归类在 JavaScript 帮助分类下。

该区块的challengeOrder数组从 Challenge 1（Vowel Balance）开始依次登记了全部挑战，Challenge 276「Offending Element」位列其中。题目数量为 365 道，与一年 365 天一一对应——这一点在种子脚本 tools/daily-challenges/seed-daily-challenges.ts 中通过EXPECTED_CHALLENGE_COUNT = 365常量做了硬性校验。

题目原文与解读

题目描述非常精炼，全文如下：

Given an array of integers that is sorted in ascending order except for one out-of-place element, return the index of that element.

• If more than one element could be considered out of place, return the index of the first one.

即：给定一个整体升序、但恰好有一个元素错位的整数数组，返回该错位元素的索引；如果存在多个可被视为错位的候选元素，则返回第一个。

这里的关键约束有两点：

1. 只有一个元素错位，其余部分依然保持升序——这是题目的前提假设，也是解题的突破口；
2. 多解时取第一个：例如[2, 1]中，删除索引 0 得到[1]、删除索引 1 得到[2]，两者删除后都满足非降序，此时必须返回索引 0。

题目没有额外指定时间复杂度要求，但作为每日一题的定位，它考察的是「对数组进行局部删减后验证有序性」的朴素模拟能力。

测试用例剖析

原文档共给出 5 组断言（hints），每一组都是一个完整的assert.equal调用，覆盖了错位元素位于头部、中部、尾部以及数组极短等场景：

assert.equal(findOffender([1, 6, 2, 3, 4, 5]), 1);

• 输入[1, 6, 2, 3, 4, 5]：6 比后面的 2 大，明显错位，其索引为1。注意：如果把 6 视为"多余"，删除它后剩余[1, 2, 3, 4, 5]完全有序。

assert.equal(findOffender([1, 2, 3, 5, 4, 5]), 3);

• 输入[1, 2, 3, 5, 4, 5]：5 > 4构成一次降序，错位元素是索引3处的 5（删除它后[1, 2, 3, 4, 5]有序）。这里也考验对"第一个"候选的判定：删除索引 4 处的 4 会得到[1, 2, 3, 5, 5]，同样是合法的，但必须返回更靠前的索引 3。

assert.equal(findOffender([2, 1]), 0);

• 输入[2, 1]：这是最短的边界用例。删除索引 0 得到[1]、删除索引 1 得到[2]，两个结果都满足非降序，依据"返回第一个"规则应返回0。

assert.equal(findOffender([2, 4, 1, 6, 8]), 2);

• 输入[2, 4, 1, 6, 8]：4 > 1构成降序，错位元素是索引2处的 1（删除后[2, 4, 6, 8]有序）。

assert.equal(findOffender([5, 18, 24, 33, 40, 55, 15, 68, 84, 91]), 6);

• 输入一个长度为 10 的数组：前六项严格递增，55 > 15出现降序，错位元素是索引6处的 15（删除后整个数组恢复升序）。这一用例验证了错位元素位于数组中后段时的处理。

题目种子代码（Seed）

原文档提供了函数骨架，要求选手在保留签名findOffender(arr)的前提下补全实现：

function findOffender(arr) { return arr; }

选手需要把默认的return arr;替换为返回错位元素索引的逻辑。这类种子代码只给出入参和占位返回，具体算法完全由选手自己设计。

解题思路：枚举删除 + 有序性验证

题目最直观、也最不容易出错的解法是暴力枚举法：

1. 依次假设索引i（从 0 开始）处的元素就是那个错位元素；
2. 把第i个元素从数组中剔除，检查剩余数组是否整体非降序（<=）；
3. 一旦找到某个i满足条件，立即返回i——由于是从前往后扫描，自然满足"返回第一个"的要求。

因为题目保证"恰好一个元素错位"，所以一定存在至少一个i满足"删除后有序"，算法必然有返回值，无需额外的兜底分支。

这一思路与仓库中 Challenge 151「Sorted Array?」等数组有序性题目一脉相承，核心都是对"非降序"（prev <= cur）这一性质的反复验证。

官方参考解答逐行解析

原文档的--solutions--区块给出了官方解答：

function findOffender(arr) { for (let i = 0; i < arr.length; i++) { const without = [...arr.slice(0, i), ...arr.slice(i + 1)]; if (without.every((n, j) => j === 0 || without[j - 1] <= n)) return i; } }

逐行拆解：

• for (let i = 0; i < arr.length; i++)：从头到尾枚举每个候选索引；
• [...arr.slice(0, i), ...arr.slice(i + 1)]：利用展开运算符与slice构造一个删除了第 i 个元素的新数组without，即arr中索引0 ~ i-1的部分拼接索引i+1 ~ 末尾的部分；
• without.every((n, j) => j === 0 || without[j - 1] <= n)：验证without是否非降序有序：
  • j === 0时跳过比较（第一个元素没有前驱）；
  • 其余位置要求without[j - 1] <= n，允许相等（题目是升序数组，但相等元素不破坏有序性）；
• return i：找到第一个满足条件的索引即返回。

关于every的一个小技巧：Array.prototype.every在回调返回false时会立即短路结束遍历，因此一旦发现某处出现prev > cur的逆序，该候选索引会被快速淘汰，无需验证完整个数组。

用测试用例手工推演

以[1, 6, 2, 3, 4, 5]为例：

• i = 0：without = [6, 2, 3, 4, 5]，6 > 2逆序，淘汰；
• i = 1：without = [1, 2, 3, 4, 5]，任意相邻项满足prev <= cur，返回1。✅

再以[5, 18, 24, 33, 40, 55, 15, 68, 84, 91]为例：

• i = 0 ~ 5时，without中都还保留着15与前面的55构成逆序，全部淘汰；
• i = 6：without = [5, 18, 24, 33, 40, 55, 68, 84, 91]严格升序，返回6。✅

复杂度分析

• 时间复杂度：最坏情况下外层循环遍历n个索引，每次构造新数组（O(n)）并调用every做一次有序性扫描（O(n)），因此总复杂度为O(n²)；
• 空间复杂度：每次迭代都会创建一个长度为n - 1的新数组without，即O(n)的辅助空间。

对于每日一题和 365 天规模的题库来说，O(n²) 的解法在输入规模较小时完全够用且正确性直观。若追求更优解，可以尝试 O(n) 时间、O(1) 空间的思路：先定位第一处逆序的相邻对，再结合该位置附近元素判断究竟是左元素错位还是右元素错位，并满足"返回第一个候选"的规则。

仓库视角：一道题如何从 Markdown 走向线上 API

这道题不仅是独立的练习，它在 freeCodeCamp 仓库中还串联起了一条完整的工程链路。理解这条链路，有助于读者把"做题"与"生产发布"对应起来。

第一步：课程 Markdown 被解析为挑战数据

题目以 Markdown 形式存放在 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/ 目录，使用 freeCodeCamp 标准的--description--、--hints--、--seed--、--solutions--分区语法编写。这些文件会被课程构建工具解析成结构化数据，并经由 Gatsby 客户端的 GraphQL 层（/___graphql端点）暴露给下游脚本。

第二步：种子脚本从 GraphQL 拉取并写入 MongoDB

tools/daily-challenges/ 目录下的脚本负责把 "dev-playground" superblock 中的题目种子化到生产/本地数据库：

• seed-daily-challenges.ts 先从 GraphQL 分别拉取 JavaScript 与 Python 两套题目，校验两边数量一致且等于365，然后从2025-08-11（UTC）起每天递增一天为每道题分配日期，最后通过bulkWrite的replaceOne + upsert写入DailyCodingChallenges集合；
• helpers.ts 中的fetchChallenges使用 GraphQL 查询superBlock: "dev-playground"且block: "daily-coding-challenges-javascript"/daily-coding-challenges-python的节点，combineChallenges则把同一道题的 JS 与 Python 版本合并为一条 Mongo 文档（并校验标题、描述与测试数量一致），文档结构包含challengeNumber、title、date、description、javascript、python等字段；
• 数据模型可参考 tools/daily-challenges/types.ts 中的Challenge类型：每个语言版本都携带tests（含testString与text）和challengeFiles（含contents与fileKey），这正是本题目中findOffender种子代码与 5 组断言被存储的形式。

运行方式见 tools/daily-challenges/README.md：复制sample.env为.env、确保依赖安装、启动带有 upcoming changes 的客户端以提供 GraphQL 服务，然后在tools/daily-challenges目录执行pnpm seed-daily-challenges。

第三步：API 按日期对外供题

种子化之后，前端通过 API 按日期获取每日挑战。相关路由位于 api/src/daily-coding-challenge/routes/daily-coding-challenge.ts，共提供 6 个公开 GET 端点：

路由层还借助 Sentry 统计了dcc.challenge_viewed、dcc.challenge_not_found等指标，用于观测每日挑战的访问情况。参数校验与响应结构定义在 api/src/daily-coding-challenge/schemas/daily-coding-challenge.ts，其中singleChallengeResponse明确给出了完整挑战文档的 JSON 形态（id、date、challengeNumber、title、description、javascript、python）。

日期处理逻辑集中在 api/src/daily-coding-challenge/utils/helpers.ts：

• getNowUsCentral/getUtcMidnight：以美国中部时间作为"今天"的基准，转成 UTC 零点；
• dateStringToUtcMidnight/monthDayStringToUtcDate：严格校验日期格式，并利用 2000 年（闰年）校验 2 月 29 日等边界；
• getSourceDate：由于只创建了 2025-08-11 至 2026-08-10 一年的题目，该函数把任意请求日期映射回这一年的源日期，实现"每年同一天返回同一道题"。

第四步：前端校验与作答

客户端侧 client/src/utils/daily-coding-challenge-validator.ts 使用 Joi 对从数据库返回的挑战文档进行结构校验，确保javascript/python各语言版本的tests（text、testString）与challengeFiles（fileKey、contents）字段完整合法，并在前端页面（如 client/src/client-only-routes/show-daily-coding-challenge.tsx）渲染题目与运行测试。

延伸思考与变体

1. 多候选的"第一个"规则：官方解法从索引 0 顺序扫描并立即返回，天然满足该规则。若改用从后往前扫描或同时找出所有合法候选，就可能违反题意，需要额外取最小值。
2. 允许相等的语义：有序性判断使用<=而非<，这是本题（以及大多数"已排序数组"类题目）的正确语义——数组允许重复元素。
3. 性能优化方向：O(n²) 解法胜在直观可靠；追求 O(n) 时可以先找出第一处逆序位置，再分别尝试"删除左邻 / 右邻"两种候选并做局部有序性验证，同时仍需遵守"返回第一个"的约束。
4. 工程化启发：一道看似简单的算法题，在 freeCodeCamp 仓库中被完整地经历了 Markdown 编写、GraphQL 抓取、365 天日期编排、MongoDB 存储、按日期/按日/按月查询的 REST API 暴露以及前端 Joi 校验等环节——这种"一份内容多端消费"的流水线设计，本身就是值得借鉴的课程内容管理范式。

综上，Challenge 276「Offending Element」用最朴素的方式训练了数组切片、展开运算符、every短路求值与"删除后有序性验证"的组合运用。掌握这道题的解法与边界分析，你就拿到了 freeCodeCamp 每日挑战体系（含种子化、API 供题与前端校验）的完整入门视角。

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp