算法笔试模拟题精解之“简单题？”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的 第54题：简单题？ 的题目解析，具体如下：

题目描述

题目等级：容易

知识点：数学

查看题目：简单题？

有一个1~n（1<=n<=100）的集合 ，现在可以让你在集合中选择任意多个数去减去一个正整数x(x是任意数)，问最少需要操作多少次可以使这个集合中的数都变为0 ？

输入一个数n(1<=100)，表示集合中的数据数量

输出最少的操作数

示例1

输入：

2

输出：

解题方法：二分法（减治法）

思路如下：二分法的核心在于，每次操作都让问题的复杂度减小为原来的一半。

若有一个1~n的集合，可以让集合中大于 n/2 的数同时减去 n/2，减完后发现所有的数会变成一个 1~n/2 的集合，也就是一次操作后整个问题的复杂度变为了原来的一半。继续同样的操作，直至问题的复杂度为0，统计这个过程中二分操作的次数即可得出最少的操作数。

时间复杂度：O(log_2 n)

空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>