Тусгай дугаар


Хэцүү байдлын түвшин Easy
Байнга асуудаг Жио MAQ o9 шийдэл холболтуудын
Тоо-цифр Сургуулийн програмчлал

Тооны талаар ямар онцгой зүйл байж болох вэ?

Үүнийг олж мэдье.

Бидэнд N тооны массив бий. Тоо нь өөрөө тооноос бусад нэг буюу хэд хэдэн тоонд хуваагддаг бол тоо онцгой байж болно.

Нэгдүгээрт, өөр зүйл рүү үсрэхээсээ өмнө цөөн хэдэн жишээн дээр үүнийг тодруулцгаая

1,2,3 массив

Тусгай дугаар 2 ба 3

Яагаад тэр вэ?

2 нь 1-т хуваагддаг ба 3-т хуваагддаг

1,2,5,9 массив

Тусгай дугаар 2,5 ба 9 байх болно

Яагаад тэр вэ?

Эдгээр тоонууд нь 1-д хуваагдах тул

2,3,4,6,8,9 массив

Тусгай дугаарууд 4.6.8.9 болно

Хоёрдугаарт, энэ асуудалд хэрхэн хандах талаар авч үзье

Тусгай дугаарын 1 хандлага

Харгис хүчин

  • Бид массиваар дамжин өнгөрдөг
  • Бид элемент тус бүрийг хуваах элементүүдийг шалгадаг

Тусгай дугаарт зориулсан Java код

// "static void main" must be defined in a public class.
public class Main 
{
    public static void diCheck(List<Integer> arr, int n) 
    { 
        Set<Integer> store = new HashSet<Integer>(); 
        for(int i=0;i<arr.size();i++)
        {
            for(int j=i+1;j<arr.size();j++)
            {
                if(arr.get(j)%arr.get(i)==0)
                    store.add(arr.get(j));
            }
        }
        for(Integer a:store)
        {
            System.out.print(a+" ");
        }
    } 
    public static void main(String[] args) 
    {
        List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5); 
        int n = arr.size(); 
        diCheck(arr, n); 
    }
}

Тусгай дугаарын C ++ код

void diCheck(int arr[], int n) 
{ 
    unordered_set<int> store; 
    int maxs = -1; 
    for (int i = 0; i < n; i++) 
    { 
        for(int j=i+1;j<n;j++)
        {
            if(arr[j]%arr[i]==0)
                store.insert(arr[j]);
        }
    } 
    for (auto x : store) 
        cout << x << " "; 
} 
int main() 
{ 
    int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    diCheck(arr, n); 
  
    return 0; 
}

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал = O (n ^ 2)

Хэрхэн?

  • Дээрх арга нь хоёр гогцоог ашигладаг
  • Нэгдүгээрт, хуваагчийн дээгүүр гарах гаднах хэсэг
  • Хоёрдугаарт. ногдол ашгийг давах дотоод
  • Энэ нь цаг хугацааны нарийн төвөгтэй байдлыг O (n ^ 2) болгоно.

Сансрын нарийн төвөгтэй байдал = O (1)

Хэрхэн?

Бид зөвхөн хувьсагч ашигладаг тул бидэнд маш их зай шаардагдахгүй

Тусгай дугаарын 2 хандлага

Хэш хүснэгт ашиглах

Нэгдүгээрт, арга барил жижиг хазуулсан хэмжээтэй, амттай хэсгүүдэд хуваана.

  • Эхлээд бүх элементүүдийг эрэмбэл
  • Хувьсагч ашиглан max элементийг ол
  • Макс элемент хэрэгтэй юу?
  • Үүнийг ашиглахын тулд тухайн тооны хуваагчдыг олох боломжтой
  • Бид num * 2-оос эхэлнэ
  • Үржвэрийг авахын тулд бид тоог өөртөө нэмнэ
  • Бид олон тоог авах бүрдээ багц болгон хадгалдаг
  • Бид олж авсан тоонуудын аль нь ч давхардсан байх ёсгүй гэдгийг баталгаажуулахын тулд тоог багцад хадгалдаг
  • Хэрэв хуваагч байгаа бол тоо нь тусгай байна
  • Тусгай дугаарыг нэмж оруулав

Хоёрдугаарт, бүх үйл явцыг даван туулах жижиг зургийг авъя. Энэ нь асуудлыг барьж авч чадаагүй хүн бүр үүнийг бүрэн ойлгодог байх болно.

Тусгай дугаар
Тусгай дугаарыг тайлбарлав

Энд байгаа улаан газрууд нь газрын зураг дээр тоонууд аль хэдийн нэмэгдсэн болохыг харуулж байна.

Java код

// "static void main" must be defined in a public class.
public class Main 
{
    public static void diCheck(List<Integer> arr, int n) 
    { 
        List<Integer> store = new ArrayList<Integer>(); 
        int max = Integer.MIN_VALUE; 
        for (int i = 0; i < n; i++) 
        { 
            store.add(arr.get(i)); 
            max = Math.max(max,arr.get(i)); 
        }
        LinkedHashSet<Integer>ans=new LinkedHashSet<Integer>();
        for(int i=0;i<n;i++)
        {
            if(arr.get(i)!=0)
            {
                for(int j=arr.get(i)*2;j<max;j++)
                {
                    if(store.contains(j))
                        ans.add(j);
                }
            }
        }
        List<Integer>ret=new ArrayList<Integer>(ans);
        for(int i=0;i<ret.size();i++)
            System.out.print(ret.get(i)+" ");
    } 
    public static void main(String[] args) 
    {
        List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5); 
        int n = arr.size(); 
        diCheck(arr, n); 
    }
}

C ++ код

void diCheck(int arr[], int n) 
{ 
    unordered_set<int> store; 
    int maxs = -1; 
    for (int i = 0; i < n; i++) 
    { 
        store.insert(arr[i]); 
        //Finding the max element 
        maxs= max(maxs, arr[i]); 
    } 
  
    // Traversing the array elements and storing the multiples
    unordered_set<int> res; 
    for (int i = 0; i < n; i++) 
    { 
        if (arr[i] != 0) 
        { 
            for (int j = arr[i] * 2; j <= maxs; j++)
            { 
                if (store.find(j) != store.end()) 
                    res.insert(j); 
            } 
        } 
    } 
    unordered_map<int, int> map; 
    for(int i = 0; i < n; i++) 
        map[arr[i]]=map[arr[i]]+1; 
  
    unordered_map<int, int>::iterator it; 
    vector<int> ans; 
    for (it = map.begin(); it != map.end(); it++) 
    { 
        if (it->second >= 2) 
        { 
            if (res.find(it->first) == res.end()) 
            { 
                int val = it->second; 
                while (val--) 
                    ans.push_back(it->first); 
            } 
        } 
  
        // If frequency is greater than 1 and is divisible by any other number 
        if (res.find(it->first) != res.end()) 
        { 
            int val = it->second; 
            while (val--) 
                ans.push_back(it->first); 
        } 
    }
    //Printing special numbers
    for (auto x : ans) 
        cout << x << " "; 
} 
int main() 
{ 
    int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    diCheck(arr, n); 
  
    return 0; 
}
1, 2, 3, 5, 8, 6, 9, 10
2,3,5,8,9,10

Тэмдэглэл: Дээрх хандлага нь зөвхөн цөөн тооны хувьд сайн ажилладаг

Тусгай дугаарын нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал = O (n ^ 2)

  • Аргачлалын цаг хугацааны нарийн төвөгтэй байдал O (n ^ 2)
  • Эрэмбэлэлт нь O (n log n) цаг хугацаа шаарддаг
  • Бид гаднах давталтыг давж, хэшээс дугаар сонгоно уу
  • Дотоод гогцоонд хуваагчдыг хайж, хэрэв байгаа бол тэдгээрийг багцад нэмнэ
  • Эцэст нь цаг хугацааны нарийн төвөгтэй байдлыг O (nlogn) + O (n ^ 2) болгож нэгтгэв.
  • N ^ 2> n logn байдлаар
  • Цаг хугацааны нарийн төвөгтэй байдал O (n ^ 2) болно

Сансрын нарийн төвөгтэй байдал = O (n)

  • Бид элементүүдийг хянахын тулд хэш болон багц ашигладаг.
  • Бидэнд n хэмжээтэй массив / ArrayList / вектор байна.
  • Тиймээс бүх элементүүдийг хадгалах орон зайг O (n) хүртэл нэгтгэдэг.

Ашигласан материал