返回不重复数的实现另类实现方式

岑韬哎 · 2025-5-29 14:52:34

原题目请参考： http://www.cnblogs.com/lovexyz123/archive/2009/09/04/1560166.html
  题目

  如果一个数字十进制表达时，不存在连续两位相同，则称之为“不重复数”。例如，105、164和198都是“不重复数”，而11、100和122不是。
  下面用一个long类型（ long类型数字A），实现返回大于A的最小“不重复数”。
  解题思路

  没有详细的统计过大家的解法（很多都在回复内贴的代码）。但感觉大家的问题主要集中在计算大数的效率上。提供一种“经验”算法供大家参考。
  题目按照我的理解，大致为输入99，返回101。输入199，返回201这类的。
  按照人类的（其实就是我的。。哈哈）解题方式，算法分析如下：
  1. 9为特殊字符
  如果这串数字的某一位和其上一位均为9，则需要返回类似“101”这样的数值。
  2. 首位和次位（左起第二位）均为9为特殊情况
  在这种情况下，需进位（增加数字一位）。
  3. 解决连续两位重复的方式为将低位数字+1（9已经当作特殊情况处理，这种情况下不可能为9）。之所以加低位是因为需要返回最小的。
  4. 任何一个数字提升（+1）后，其所有次位（例如1881111中的188变为189，所有次位为1111）都变得不重要。根据“经验”可得知，最小数为所有前位（189）加上（0101）。其中“0101”为固定不重复最小值，其长度与数字所有次位的长度相同，以0开头，用1间隔（依据“不重复数”条件分析而来）。
  5. 由于可能在“99”处理后造成前一位与前两位重复（例如12199变为12201，造成了新的重复），在处理完成后重新调用函数自身进行二次处理。中断条件为结果字串中未发现重复的两位（即“不重复数”）。
  如果按照此思路进行解题运算，大多数情况下算法复杂度只为O(n) (我其实不会算算法复杂度，高手可以提示一下这种算法的复杂度该如何计算。只是要表达和长度相关的意思)
  代码全文

1: using System;

复制代码

2: using System.Collections.Generic;

复制代码

3: using System.Linq;

复制代码

4: using System.Text;

复制代码

5: using System.Text.RegularExpressions;

复制代码

6: using System.Collections.ObjectModel;

复制代码

7:

复制代码

8: namespace SubStringFrequency

复制代码

9: {

复制代码

10: class Program

复制代码

11: {

复制代码

12: static void Main(string[] args)

复制代码

13: {

复制代码

14: var consoleInput = Console.ReadLine();

复制代码

15: long baseNumber = long.Parse(consoleInput);

复制代码

16:

复制代码

17: Console.WriteLine(getAvaliableNum(baseNumber));

复制代码

18: }

复制代码

19:

复制代码

20: private static string getAvaliableNum(long consoleInput)

复制代码

21: {

复制代码

22: if (consoleInput < 10) //single number

复制代码

23: {

复制代码

24: return consoleInput.ToString();

复制代码

25: }

复制代码

26:

复制代码

27: string temp = consoleInput.ToString();

复制代码

28: var reach = 0;

复制代码

29: StringBuilder result = new StringBuilder();

复制代码

30: for (int i = 1; i < temp.Length; i++)

复制代码

31: {

复制代码

32: var currentNum = temp[i];

复制代码

33: var nextNum = temp[i - 1];

复制代码

34: if (currentNum == nextNum)

复制代码

35: {

复制代码

36: reach += 1;

复制代码

37: if (currentNum == '9')

复制代码

38: {

复制代码

39: if (i == 1)

复制代码

40: {

复制代码

41: result.Append('1');

复制代码

42: result.Append(getMimimumUniqueNumByLength(temp.Length));

复制代码

43: break;

复制代码

44: }

复制代码

45: else

复制代码

46: {

复制代码

47: var hiNumber = int.Parse(result[result.Length - 1].ToString()) + 1;

复制代码

48: result.Remove(result.Length - 1, 1);

复制代码

49: result.Append(hiNumber);

复制代码

50: result.Append(getMimimumUniqueNumByLength(temp.Length - i + 1));

复制代码

51: break;

复制代码

52: }

复制代码

53: }

复制代码

54: else

复制代码

55: {

复制代码

56: result.Append(nextNum);

复制代码

57: result.Append(int.Parse(currentNum.ToString()) + 1);

复制代码

58: result.Append(getMimimumUniqueNumByLength(temp.Length - i - 1));

复制代码

59: break;

复制代码

60: }

复制代码

61:

复制代码

62: }

复制代码

63: else

复制代码

64: {

复制代码

65: result.Append(nextNum);

复制代码

66: if (i == temp.Length - 1)

复制代码

67: {

复制代码

68: result.Append(currentNum);

复制代码

69: }

复制代码

70: }

复制代码

71: }

复制代码

72:

复制代码

73: var resultString = string.Empty;

复制代码

74:

复制代码

75: if (reach > 0)

复制代码

76: {

复制代码

77: resultString = getAvaliableNum(long.Parse(result.ToString()));

复制代码

78: }

复制代码

79: else

复制代码

80: {

复制代码

81: resultString = result.ToString();

复制代码

82: }

复制代码

83: return resultString;

复制代码

84: }

复制代码

85:

复制代码

86: private static string getMimimumUniqueNumByLength(int length)

复制代码

87: {

复制代码

88: StringBuilder sb = new StringBuilder();

复制代码

89: var temp = 0;

复制代码

90: for (int i = 0; i < length; i++)

复制代码

91: {

复制代码

92: sb.Append(temp);

复制代码

93: if (temp == 0)

复制代码

94: {

复制代码

95: temp = 1;

复制代码

96: }

复制代码

97: else if (temp == 1)

复制代码

98: {

复制代码

99: temp = 0;

复制代码

100: }

复制代码

101: }

复制代码

102: return sb.ToString();

复制代码

103: }

复制代码

104: }

复制代码

105: }

复制代码

结论

处理121989999991999只用一瞬间。就没有统计时间了。未进行溢出处理。
欢迎大家指正讨论。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

返回不重复数的实现另类实现方式

浏览过的版块

签约作者

返回不重复数的实现 另类实现方式

浏览过的版块

签约作者

返回不重复数的实现另类实现方式