我必須在未排序的序列中找到缺失的編號。這個序列存儲在一個String對象中。例如,在此序列中:3 1 6 5 2
缺少的編號是4
。 每個數字之間都有一個\n
。我必須這樣做,而不使用數組,字典,列表等結構,因爲我需要具有O(1)複雜性。 在輸入我也收到序列的最大數量(在示例序列中,我收到數字6) 任何想法?在未排序的序列中查找缺少的編號
-2
A
回答
0
方法1(用求和公式) 算法:
- 獲取數字 的總和= N *(N + 1)/ 2 ----------- O(1)
2減去全部來自總和的數量和 你會得到失蹤人數
void ans(int total){ ///O(1)
big_total = (n+1)*(n+2)/2; // n+1 because 1 number is missing
return (big_total-total);
}
input_array()
{
int n,total=0,i;
cout<<"enter no of element";
cin>>n;
for(i=0;i<n;i++)
{
cin>>arr[i];
total+=arr[i];
}
cout<<ans(total);
}
+0
不應該你的大總數是n *((n + 1)/ 2) ? –
+0
比'arr [] = {1,3,4,5}'說'n = 4'比我們使用'n + 1'要好,因爲一個數字丟失了,所以總數是'5' –
+0
是的,說不允許使用陣列和最大數量給予。所以最大數量應該是n而不需要數組。 –
相關問題
- 1. 查找缺少的序列號
- 2. 僅查找缺少序號的序列號
- 3. 查找序列中缺少的數字
- 4. 使用.reduce查找序列中的缺失編號
- 5. 查找排序的數組中缺少的元素
- 6. 查找升序編號的最長序列中排序的數組
- 7. Mysql,在一個序列中查找缺少的數字
- 8. 數組 - 在序列中查找缺少的數字
- 9. 在無序列表中查找缺少的數字
- 10. Android查找缺少號碼
- 11. SQL - 在大多數有序連續序列中查找缺少的int值
- 12. 有效查找未排序序列中的重複項
- 13. 查找列缺號
- 14. 如何編寫查詢來查找缺少的號碼?
- 15. 查找CD的序列號
- 16. 如何提高我的程序以查找未排序數組中缺少的最小正數?
- 17. 在未排序數組中查找值
- 18. 選擇排序不穩定後在代碼排序陣列中查找編號的位置的代碼?
- 19. 如何在數字序列中找到缺少的數字?
- 20. 缺少序列化或編碼
- 21. 排序編號
- 22. 查找順序編號
- 23. 查找數組中的序列號
- 24. jQuery tablesorter,有編號的排序列
- 25. Oracle序列排除指定的編號
- 26. 查找排序列表
- 27. 在Timesstamp中查找缺少的數據
- 28. 在Netsuite中查找缺少的發票
- 29. 上的行排序號升序排列
- 30. 在HSQL中缺少測試序列
向我們展示您的代碼或嘗試執行此問題的距離。 – Gatusko
O(1)的複雜性只有在序列長度的上限纔有可能。否則,你會遇到O(n * log n)(即先排序並查找缺少的數字)。或者也許O(n)如果你不關心空間。 – Ctx
比較序列的總和與最小值和最大值之間的整數之和。 –